Valid Palindrome 🧠
LeetCode Link: Valid Palindrome
Difficulty: Easy
Problem Explanation 📝
Problem: LeetCode 125 - Valid Palindrome
Description: Given a string s, determine if it is a palindrome, considering only alphanumeric characters and ignoring cases.
Intuition: To check if a string is a palindrome, we need to compare characters from both ends of the string. We can ignore non-alphanumeric characters and treat uppercase and lowercase letters as the same.
Approach:
- Initialize two pointers,
left
pointing to the start of the string, andright
pointing to the end of the string. - Iterate while
left
is less thanright
:
- Skip non-alphanumeric characters by incrementing
left
or decrementingright
if the character at that position is not alphanumeric. - Convert both characters to lowercase and compare them. If they are not equal, return false.
- Increment
left
and decrementright
to move to the next pair of characters.
- If the loop completes without finding any non-matching characters, return true.
⌛ Time Complexity: The time complexity is O(n), where n is the length of the input string. We iterate through the string once to check if it is a valid palindrome.
💾 Space Complexity: The space complexity is O(1) since we are using a constant amount of space to store the pointers and perform the comparison.
Solutions 💡
Cpp 💻
class Solution {
public:
bool isPalindrome(string s) {
int left = 0, right = s.length() - 1;
while (left < right) {
// isalnum -> Is alphabet or number
if (!isalnum(s[left])) {
left++;
continue;
}
if (!isalnum(s[right])) {
right--;
continue;
}
if (tolower(s[left]) != tolower(s[right])) {
return false;
}
left++;
right--;
}
return true;
}
};
Python 🐍
class Solution:
def isPalindrome(self, s: str) -> bool:
left, right = 0, len(s) - 1
while left < right:
while left < right and not s[left].isalnum():
left += 1
while left < right and not s[right].isalnum():
right -= 1
if s[left].lower() != s[right].lower():
return False
left += 1
right -= 1
return True