LeetCode #125: Valid Palindrome

LeetCode Solutions

https://leetcode.com/problems/valid-palindrome/

To solve this problem, we can use two pointers, one at the beginning and one at the end of the input string. We can compare the characters at the two pointers, moving them towards each other until they meet in the middle. We can ignore any non-alphanumeric characters and consider only lowercase characters when comparing the characters at the two pointers. If all the characters match, the input string is a palindrome.

Steps to solve the problem:

  1. Create a function called “isPalindrome” that takes a string s as input.
  2. Create two pointers, one at the beginning of the input string and one at the end of the input string.
  3. Convert the input string to lowercase using the lower() method.
  4. While the left pointer is less than or equal to the right pointer:
  5. If the characters at the two pointers are equal, increment the left pointer and decrement the right pointer.
  6. If the character at the left pointer is a non-alphanumeric character or a space, increment the left pointer.
  7. If the character at the right pointer is a non-alphanumeric character or a space, decrement the right pointer.
  8. If the characters at the two pointers are not equal and are alphanumeric, return False.
  9. If all the characters match, the input string is a palindrome. Return True.

Python Code: Here’s the Python code to solve the Valid Palindrome problem:

class Solution:
    def isPalindrome(self, s: str) -> bool:
        left = 0
        right = len(s)-1
        s = s.lower()
        while left <= right:
            if s[left] == s[right]:
                left+=1
                right-=1
                continue
            elif s[left] == " " or not s[left].isalnum():
                left+=1
                continue
            elif s[right] == " " or not s[right].isalnum():
                right-=1
                continue
            else:
                return False
        return True

Time and Space Complexity:

The time complexity of this solution is O(n), where n is the length of the input string. This is because we need to iterate through the input string once to compare the characters at the two pointers.

The space complexity of this solution is O(1), as we are using constant extra space to store the two pointers.