Valid Palindrome - LeetCode Problem

Problem Description

Leetcode problem Valid Palindrome asks you to determine if a given string is a valid palindrome or not. A palindrome is a word, phrase, or sequence of characters that reads the same forwards and backward. For example, "racecar" and "level" are palindromes.

The input string may contain letters, digits, and non-alphanumeric characters. We need to ignore non-alphanumeric characters and consider only alphanumeric characters (letters and digits).

Solution

To solve this problem, we can use the two-pointer approach. We can start from the beginning and end of the string and compare the characters at each position. If the characters are not the same, we can immediately return false. We can continue this process until we reach the middle of the string.

We can use the isalnum() method to check if a character is alphanumeric or not. This method returns True if the character is an alphabet or a digit, otherwise False.

Here's the step-by-step solution in Python:

def isPalindrome(s: str) -> bool:
    i, j = 0, len(s) - 1

    while i < j:
        while i < j and not s[i].isalnum():
            i += 1
        while i < j and not s[j].isalnum():
            j -= 1

        if s[i].lower() != s[j].lower():
            return False

        i += 1
        j -= 1

    return True

We start with two pointers i and j pointing to the first and last character of the string, respectively. We iterate over the string using a while loop while i is less than j. We check if the characters at i and j are alphanumeric using the isalnum() method. If either of them is not alphanumeric, we move the corresponding pointer toward the center of the string until we find an alphanumeric character.

Once we find two alphanumeric characters at i and j, we convert them to lowercase using the lower() method and compare them. If they are not the same, we return False. If they are the same, we move i one step forward and j one step backward.

We continue this process until i is no longer less than j. If we haven't returned False before reaching the end of the string, it means that the string is a valid palindrome, and we return True.

Complexity Analysis

The time complexity of this solution is O(N), where N is the length of the input string. We traverse the string once and perform constant time operations at each step.

The space complexity of this solution is O(1), as we are not using any extra space other than the input string.

Conclusion

In this blog post, we learned how to solve the Valid Palindrome problem using the two-pointer approach in Python. We also learned how to check if a character is alphanumeric using the isalnum() method and convert a character to lowercase using the lower() method. I hope this post was helpful to you, and you now feel more confident in solving similar problems. Happy coding!😎