Write a Java method to check whether a string is a palindrome, ignoring case and non-letters.
SHORT ANSWER
Use two pointers from both ends, skip anything that is not a letter or digit, compare lowercase characters, and move inward. It runs in O(n) time with O(1) extra space.
Explain it simply
The idea is to walk inward from both ends, ignoring spaces and punctuation, so that "Madam, I'm Adam" counts as a palindrome. We never build a cleaned copy, which saves memory.
Line by line
java
public static boolean isPalindrome(String s) {
int i = 0, j = s.length() - 1;
while (i < j) {
char a = s.charAt(i), b = s.charAt(j);
if (!Character.isLetterOrDigit(a)) { i++; continue; } // skip junk on the left
if (!Character.isLetterOrDigit(b)) { j--; continue; } // skip junk on the right
if (Character.toLowerCase(a) != Character.toLowerCase(b)) return false;
i++;
j--;
}
return true;
}
// isPalindrome("Madam, I'm Adam") returns true
// isPalindrome("Rohit") returns falseEach loop either skips one character or compares a pair and moves both pointers, so every character is looked at once.
Complexity
Time O(n), space O(1).
What to say in the interview
"I use two pointers from the ends, skip non-alphanumeric characters, and compare in lowercase. I avoid reversing the string into a new one because that costs extra memory. I would also mention the empty string and a single character return true."
Common mistakes
- Comparing with
==on String objects instead of char values. - Forgetting to skip punctuation, so phrases wrongly fail.