The goal of this problem is to determine whether a given string is a palindrome, considering only alphanumeric characters and ignoring cases. A palindrome reads the same forward and backward after removing non-alphanumeric characters.
Steps
- Convert the string to lowercase to ensure case-insensitive comparison.
- Traverse each character in the string.
- Keep only alphanumeric characters using ASCII code checks.
- Build a filtered version and its reverse simultaneously.
- Return true if both strings are equal, else return false.
Dry Run
Input: s = "Race a Car"
- Lowercase:
"race a car" - Filtered alphanumerics:
"raceacar" - Reverse:
"racacear" -
Since
"raceacar"≠"racacear", returnfalse
Time & Space Complexity
- Time Complexity: O(n), where n is the length of the input string
- Space Complexity: O(n), due to additional filtered and reversed strings
var isPalindrome = function (s) {
s = s.toLowerCase();
let filteredString = "";
let rev = "";
for (let i = 0; i < s.length; i++) {
if (
(s[i].charCodeAt() >= "a".charCodeAt() && s[i].charCodeAt() <= "z".charCodeAt()) ||
(s[i].charCodeAt() >= "0".charCodeAt() && s[i].charCodeAt() <= "9".charCodeAt())
) {
filteredString = filteredString + s[i];
rev = s[i] + rev;
}
}
return filteredString === rev;
};
#include <iostream>
#include <cctype>
using namespace std;
bool isPalindrome(string s) {
string filtered = "", rev = "";
for (char c : s) {
if (isalnum(c)) {
char lower = tolower(c);
filtered += lower;
rev = lower + rev;
}
}
return filtered == rev;
}
#include <stdio.h>
#include <ctype.h>
#include <string.h>
int isPalindrome(char* s) {
char filtered[1000] = "", rev[1000] = "";
int fIdx = 0, rIdx = 0;
for (int i = 0; s[i]; i++) {
if (isalnum(s[i])) {
char c = tolower(s[i]);
filtered[fIdx++] = c;
}
}
for (int i = fIdx - 1; i >= 0; i--) {
rev[rIdx++] = filtered[i];
}
filtered[fIdx] = '\0';
rev[rIdx] = '\0';
return strcmp(filtered, rev) == 0;
}
public class Solution {
public boolean isPalindrome(String s) {
StringBuilder filtered = new StringBuilder();
StringBuilder rev = new StringBuilder();
for (char c : s.toCharArray()) {
if (Character.isLetterOrDigit(c)) {
char lower = Character.toLowerCase(c);
filtered.append(lower);
rev.insert(0, lower);
}
}
return filtered.toString().equals(rev.toString());
}
}
def isPalindrome(s: str) -> bool:
filtered = ""
rev = ""
for c in s:
if c.isalnum():
c = c.lower()
filtered += c
rev = c + rev
return filtered == rev
