We can use Two Pointers starting from both ends of the string. We skip non-alphanumeric characters and compare the characters (case-insensitive). If they mismatch, it’s not a palindrome.
// Pseudocode: Create a new string with only alphanumeric characters, reversed, and compare.
// 1. Filter string to only lowercased alphanumeric.
// 2. Return filtered == reversed_filtered.
class Solution {
public:
bool isPalindrome(string s) {
string filtered = "";
for (char c : s) {
if (isalnum(c)) {
filtered += tolower(c);
}
}
string reversed_filtered = filtered;
reverse(reversed_filtered.begin(), reversed_filtered.end());
return filtered == reversed_filtered;
}
};// Pseudocode:
// 1. Init l = 0, r = s.length() - 1.
// 2. Loop while l < r:
// 3. While l < r and not isalnum(s[l]), l += 1.
// 4. While l < r and not isalnum(s[r]), r -= 1.
// 5. If tolower(s[l]) != tolower(s[r]), return False.
// 6. l += 1, r -= 1.
// 7. Return True.
class Solution {
public:
bool isPalindrome(string s) {
int l = 0, r = s.length() - 1;
while (l < r) {
while (l < r && !isalnum(s[l])) {
l++;
}
while (r > l && !isalnum(s[r])) {
r--;
}
if (tolower(s[l]) != tolower(s[r])) {
return false;
}
l++;
r--;
}
return true;
}
};Time: O(n) because we iterate through the string once. Space: O(1) as we use two pointers instead of creating a new string.
- Empty string or string with only spaces/punctuation. Returns True.
- Mixed case and numbers. Handled by tolower() and isalnum().
Always implement your own isalnum logic in interviews to show you understand ASCII values, or at least mention it. Using built-in functions is fine, but knowing the underlying logic is impressive.