Input: s ="A man, a plan, a canal: Panama"Output: trueExplanation: "amanaplanacanalpanama"is a palindrome.
Example 2:
1
2
3
Input: s ="race a car"Output: falseExplanation: "raceacar"is not a palindrome.
Example 3:
1
2
3
4
Input: s = " "
Output: true
Explanation: s is an empty string "" after removing non-alphanumeric characters.
Since an empty string reads the same forward and backward, it is a palindrome.
Have you consider that the string might be empty? This is a good question to ask during an interview.
For the purpose of this problem, we define empty string as valid palindrome.
From start and end loop though the string, i.e., char array. If it is not alpha or number, increase or decrease pointers. Compare the alpha and numeric characters. The solution below is pretty straightforward.
classSolution {
publicbooleanisPalindrome(String s) {
// Preprocess the string using regex: remove non-alphanumeric characters and convert to lowercase String cleaned = s.replaceAll("[^a-zA-Z0-9]", "").toLowerCase();
// Compare the cleaned string with its reversereturn cleaned.equals(new StringBuilder(cleaned).reverse().toString());
}
}
1
2
3
4
5
6
7
classSolution:
defisPalindrome(self, s: str) -> bool:
# Preprocess the string using regex cleaned = re.sub(r"[^a-zA-Z0-9]", "", s).lower() # Remove non-alphanumeric characters and convert to lowercase# Compare the cleaned string with its reversereturn cleaned == cleaned[::-1]
Method 2 - Removing non-alphanumeric chars manually and loop till middle#
classSolution {
publicbooleanisPalindrome(String s) {
// Preprocess the string: create a clean string manually StringBuilder cleaned =new StringBuilder();
for (char c : s.toCharArray()) {
if (Character.isLetterOrDigit(c)) { // Check if the character is alphanumeric cleaned.append(Character.toLowerCase(c)); // Add lowercase version to the cleaned string }
}
// Iterate to the middleint n = cleaned.length();
for (int i = 0; i < n / 2; i++) {
if (cleaned.charAt(i) != cleaned.charAt(n - 1 - i)) { // Compare characters at start and endreturnfalse; // If mismatch occurs, return False }
}
returntrue; // If loop completes, return True }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
classSolution:
defisPalindrome(self, s: str) -> bool:
# Preprocess the string: create a clean string manually cleaned =""for char in s:
if char.isalnum(): # Check if the character is alphanumeric cleaned += char.lower() # Add lowercase version to the new string# Iterate to the middle n = len(cleaned)
for i in range(n //2): # Compare up to the middle of the stringif cleaned[i] != cleaned[n -1- i]: # Compare characters at start and endreturnFalse# If mismatch occurs, return FalsereturnTrue# If loop completes, return True
Method 3 - Removing non-alphanumeric chars and using 2 Pointers#
classSolution {
publicbooleanisPalindrome(String s) {
// Step 1: Build the cleaned string manually StringBuilder cleaned =new StringBuilder();
for (char c : s.toCharArray()) {
if (Character.isLetterOrDigit(c)) { // Use a custom method to check if it's alphanumeric cleaned.append(Character.toLowerCase(c)); // Use a custom method to convert to lowercase }
}
// Step 2: Use two pointers to check for palindromeint left = 0, right = cleaned.length() - 1;
while (left < right) {
if (cleaned.charAt(left) != cleaned.charAt(right)) { // Compare characters at both pointersreturnfalse; // If mismatch, return false }
left++; // Move left pointer inward right--; // Move right pointer inward }
returntrue; // If no mismatches, string is a palindrome }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
classSolution:
defisPalindrome(self, s: str) -> bool:
# Preprocess the string: create a clean string manually cleaned =""for char in s:
if char.isalnum(): # Check if the character is alphanumeric cleaned += char.lower() # Add its lowercase version to the new string# Initialise two pointers left, right =0, len(cleaned) -1# Compare characters at each pointerwhile left < right:
if cleaned[left] != cleaned[right]: # If mismatch, return FalsereturnFalse left +=1 right -=1returnTrue# If the loop completes, return True
classSolution {
publicbooleanisPalindrome(String s) {
int l = 0, r = s.length() - 1;
while (l < r) {
while (l < r &&!Character.isLetterOrDigit(s.charAt(l))) {
l++;
}
while (l < r &&!Character.isLetterOrDigit(s.charAt(r))) {
r--;
}
if (Character.toLowerCase(s.charAt(l)) != Character.toLowerCase(s.charAt(r))) {
returnfalse;
}
l++;
r--;
}
returntrue;
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
classSolution:
defis_palindrome(self, s: str) -> bool:
l, r =0, len(s) -1while l < r:
while l < r andnot s[l].isalnum():
l +=1while l < r andnot s[r].isalnum():
r -=1if s[l].lower() != s[r].lower():
returnFalse l +=1 r -=1returnTrue
classSolution {
publicbooleanisPalindrome(String s) {
int l = 0, r = s.length() - 1;
while (l < r) {
while (l < r &&!myIsLetterOrDigit(s.charAt(l))) {
l++;
}
while (l < r &&!myIsLetterOrDigit(s.charAt(r))) {
r--;
}
if (myToLowerCase(s.charAt(l)) != myToLowerCase(s.charAt(r))) {
returnfalse;
}
l++;
r--;
}
returntrue;
}
// UDF to check if a character is alphanumericprivatebooleanisLetterOrDigit(char c) {
return (c >='a'&& c <='z') || (c >='A'&& c <='Z') || (c >='0'&& c <='9');
}
// UDF to convert uppercase to lowercaseprivatechartoLowerCase(char c) {
if (c >='A'&& c <='Z') {
return (char) (c + 32); // Add 32 to ASCII value for conversion }
return c; // Return as-is for lowercase letters or non-letters }
}
classSolution:
defisPalindrome(self, s: str) -> bool:
l, r =0, len(s) -1while l < r:
while l < r andnot self.isalnum(s[l]):
l +=1while l < r andnot self.isalnum(s[r]):
r -=1if self.lower(s[l]) != self.lower(s[r]):
returnFalse l +=1 r -=1returnTrue# UDF to check if a character is alphanumericdefisalnum(self, char: str) -> bool:
return ('a'<= char <='z') or \
('A'<= char <='Z') or \
('0'<= char <='9')
# UDF to convert uppercase to lowercasedeflower(self, char: str) -> str:
if'A'<= char <='Z':
return chr(ord(char) +32) # Add 32 to ASCII value for conversionreturn char # Return as-is for lowercase letters or non-letters