Leetcode 125 - Valid Palindrome
Explanation for Leetcode 125 - Valid Palindrome problem, and its solution in Python.
Problem
Leetcode 125 - Valid Palindrome
Example:
1
2
3
4
5
6
7
Input: s = "A man, a plan, a canal: Panama"
Output: true
Explanation: "amanaplanacanalpanama" is a palindrome.
Input: s = "race a car"
Output: false
Explanation: "raceacar" is not a palindrome.
Approach
Since we are checking if the string is a palindrome, we must first remove all non-alphanumeric characters and convert the string to lowercase. Then, we can have two pointers, one at the beginning and one at the end of the string, and compare the characters at the two pointers. If the characters are not the same, return false. If the characters are the same, move the pointers towards the center of the string. If we make it through the string without finding any mismatched characters, return true.
Visual representation of the approach:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
s = "race a car"
After removing non-alphanumeric characters and converting to lowercase:
s = "raceacar"
Two pointers:
left = 0
right = 7
s[left] = 'r'
s[right] = 'r'
Since s[left] == s[right], move the pointers towards the center:
left = 1
right = 6
s[left] = 'a'
s[right] = 'a'
Since s[left] == s[right], move the pointers towards the center:
left = 2
right = 5
s[left] = 'c'
s[right] = 'c'
Since s[left] == s[right], move the pointers towards the center:
left = 3
right = 4
s[left] = 'e'
s[right] = 'a'
Since s[left] != s[right], we return false.
Here is the implementation of the approach:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution:
def isPalindrome(self, s: str) -> bool:
# remove all non-alphanumeric characters and convert to lowercase
s = ''.join(char.lower() for char in s if char.isalnum())
# two pointers
left, right = 0, len(s)-1
while left <= right:
if s[left] != s[right]:
return False
left += 1
right -= 1
return True
Time Complexity and Space Complexity
The time complexity is $ O(n) $ since we are iterating through the string once.
The space complexity is $ O(1) $ since we are not using any additional space.