Valid Palindrome
A phrase is a palindrome if, after turning every uppercase letter into lowercase and removing every character that is not a letter or a digit, it reads the same forward and backward. Given a string strue
Example 1
Output: true
Explanation: "amanaplanacanalpanama" is a palindrome.
Example 2
Output: false
Explanation: "raceacar" is not a palindrome.
Example 3
Output: true
Explanation: after cleaning, the string is empty, and an empty string reads the same both ways.
How to Think About It
Step 1: The simple way
Build a cleaned, lowercase copy of the string, then compare it with its reverse. That works but uses O(n) extra space.
Step 2: Compare from both ends instead
A palindrome's first character matches its last, its second matches its second to last, and so on. Put lohi
Step 3: Skip what does not count
At each step:
- if
is not a letter or digit, moves[lo] right and try again;lo - if
is not a letter or digit, moves[hi] left and try again;hi - otherwise compare them ignoring case. A mismatch means it is not a palindrome. A match moves both pointers inward.
If the pointers meet without a mismatch, the string is a palindrome.
Walkthrough
s = "race a car"
| lo (char) | hi (char) | Decision |
|---|---|---|
| 0 (r) | 9 (r) | match |
| 1 (a) | 8 (a) | match |
| 2 (c) | 7 (c) | match |
| 3 (e) | 6 (space) | skip the space on the right |
| 3 (e) | 5 (a) | e ≠ a: return false |
Java Solution
The method compares characters from both ends, skipping anything that is not a letter or a digit:
- One step per pass: each pass either skips one character on one side or compares a pair, so no character is jumped over.
- Digits count:
keeps digits, so "0P" compares '0' with 'P' and returnsCharacter.isLetterOrDigit .false - Case:
on both sides makes "Aa" a palindrome.Character.toLowerCase - Nothing to compare: " " or ".,;" skip until the pointers meet and return
, as the problem requires for an empty cleaned string.true
Using Character.isLettertrue
public class ValidPalindrome {
public static boolean isPalindrome(String s) {
int lo = 0;
int hi = s.length() - 1;
while (lo < hi) {
char a = s.charAt(lo);
char b = s.charAt(hi);
if (!Character.isLetterOrDigit(a)) {
lo++; // skip spaces and punctuation
} else if (!Character.isLetterOrDigit(b)) {
hi--;
} else if (Character.toLowerCase(a) != Character.toLowerCase(b)) {
return false;
} else {
lo++;
hi--;
}
}
return true;
}
public static void main(String[] args) {
System.out.println(isPalindrome("A man, a plan, a canal: Panama")); // true
System.out.println(isPalindrome("race a car")); // false
System.out.println(isPalindrome(" ")); // true
}
}
The original implementation,
Complexity
- Time: O(n).
only moves right andlo only moves left, so the loop runs at most n times with one check per pass.hi - Space: O(1). Two indices and two chars; no cleaned copy of the string is built, which would cost O(n).
If one character may be deleted, see