JavaScript Solutions:
class Solution {
// Solution using regular expression
isPalindrome(s) {
s = s.toLowerCase().replace(/[^a-z0-9]/g, '');
return s === s.split('').reverse().join('');
}
// Time: O(n), Space: O(n)
// Solution with two pointers
isPalindromePointers(s) {
let left = 0;
let right = s.length - 1;
while (left < right) {
while (left < right && !this.isAlphanumeric(s[left])) {
left++;
}
while (left < right && !this.isAlphanumeric(s[right])) {
right--;
}
if (s[left].toLowerCase() !== s[right].toLowerCase()) {
return false;
}
left++;
right--;
}
return true;
}
isAlphanumeric(char) {
return /[a-zA-Z0-9]/.test(char);
}
// Time: O(n), Space: O(1)
}
Python Solutions:
class Solution:
# Solution using built-in functions
def isPalindrome(self, s: str) -> bool:
# Filter only letters and digits, convert to lowercase
filtered_chars = [char.lower() for char in s if char.isalnum()]
return filtered_chars == filtered_chars[::-1]
# Time: O(n), Space: O(n)
# Solution with two pointers
def isPalindromePointers(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
# Time: O(n), Space: O(1)
Java Solutions:
class Solution {
// Solution using StringBuilder
public boolean isPalindrome(String s) {
StringBuilder filtered = new StringBuilder();
for (char c : s.toCharArray()) {
if (Character.isLetterOrDigit(c)) {
filtered.append(Character.toLowerCase(c));
}
}
String filteredStr = filtered.toString();
return filteredStr.equals(new StringBuilder(filteredStr).reverse().toString());
}
// Time: O(n), Space: O(n)
// Solution with two pointers
public boolean isPalindromePointers(String s) {
int left = 0;
int right = s.length() - 1;
while (left < right) {
while (left < right && !Character.isLetterOrDigit(s.charAt(left))) {
left++;
}
while (left < right && !Character.isLetterOrDigit(s.charAt(right))) {
right--;
}
if (Character.toLowerCase(s.charAt(left)) !=
Character.toLowerCase(s.charAt(right))) {
return false;
}
left++;
right--;
}
return true;
}
// Time: O(n), Space: O(1)
}
Approach Explanations:
-
String Transformation Approach:
- Remove all characters except letters and digits
- Convert string to lowercase
- Compare string with its reversed version
- Advantage: simple implementation
- Disadvantage: requires additional memory
-
Two Pointers Approach:
- Use two pointers from start and end of string
- Skip non-alphanumeric characters
- Compare characters in lowercase
- Advantage: optimal memory usage
- Disadvantage: more complex implementation