# Valid Palindrome Problem

0 like 0 dislike
375 views

Given a string, determine if it is a palindrome, considering only alphanumeric characters and ignoring cases.

Note: For the purpose of this problem, we define empty string as valid palindrome.

Example 1:

```Input: "A man, a plan, a canal: Panama"
Output: true
```

Example 2:

```Input: "race a car"
Output: false
```

Constraints:

• `s` consists only of printable ASCII characters.

0 like 0 dislike
by Goeduhub's Expert (2.3k points)

One way to solve this problem is to create new string with only alphanumeric symbols and then check if it is palindrome. However we need O(n) space for this. There is more subtle approach, using Two Pointers technique.

• Start with beg = 0 and end = len(s) - 1, the first and the last symbols of string s.
• Now, we are going to move iterator beg only to the right and iterator end only to the left. Let us move them, until we reach alphanumeric symbols, using isalnum() function.
• Compare these two symbols. We are happy, if they are equal, or it is the same letter in different capitalization, for example q and Q. How to check this case? Make both symbols capitalized, using .upper() and compare them.
• In opposite case, immidietly return False.
• If we reached the end of or program and we did not return False, then we need to return True.

Complexity: Time complexity is O(n), because we move beg only to the right and end only to the left, until they meet. Space complexity is O(1), we just use a couple of additional variables.

class Solution:

def isPalindrome(self, s):

beg, end = 0, len(s) - 1

while beg <= end:

while not s[beg].isalnum() and beg < end: beg += 1

while not s[end].isalnum() and beg < end: end -= 1

if s[beg] == s[end] or s[beg].upper() == s[end].upper():

beg, end = beg + 1, end - 1

else:

return False

return True

eg : ans = Solution()

ans.isPalindrome("race a car")

Output -

False

Learn & Improve In-Demand Data Skills Online in this Summer With  These High Quality Courses[Recommended by GOEDUHUB]:-

Best Data Science Online Courses[Lists] on:-

Claim your 10 Days FREE Trial for Pluralsight.