Valid Palindrome
Given a string, determine if it is a palindrome, considering only alphanumeric characters and ignoring case.
Constraints:
- 1 <= s.length <= 2 * 10^5
- s consists only of printable ASCII characters.
Examples:
Input: A man, a plan, a canal: Panama
Output: true
Explanation: Ignoring non-alphanumeric characters and case, the string reads the same backward as forward.
Input: Not a palindrome
Output: false
Explanation: The string does not read the same backward as forward.
Solutions
Two Pointers
The two pointers approach involves initializing two pointers, one at the start and one at the end of the string. We then compare the characters at these positions, ignoring non-alphanumeric characters and considering case insensitivity. If the characters match, we move the pointers closer to the center. If they do not match, we return false. If the loop completes without finding any mismatches, we return true.
function isPalindrome(s) {
let left = 0,
right = s.length - 1;
while (left < right) {
if (!isAlphanumeric(s[left])) {
left++;
} else if (!isAlphanumeric(s[right])) {
right--;
} else if (s[left].toLowerCase() !== s[right].toLowerCase()) {
return false;
} else {
left++;
right--;
}
}
return true;
}
function isAlphanumeric(char) {
return /^[a-zA-Z0-9]$/.test(char);
}
Follow-up:
How would you solve this problem if the string is very large and does not fit into memory?
