Given a string s, return true if it is a palindrome considering only alphanumeric characters and ignoring case.
Input: "A man, a plan, a canal: Panama" → Output: trueInput: "race a car" → Output: false
Two pointers from both ends. Skip non-alphanumeric characters. Compare lowercase versions of characters at both pointers.
- lo=0, hi=s.length()-1.
- While lo
- Compare Character.toLowerCase(s[lo]) with s[hi].
- If mismatch return false; else lo++, hi--.
class Solution {
public boolean isPalindrome(String s) {
int lo = 0, hi = s.length() - 1;
while (lo < hi) {
while (lo < hi && !Character.isLetterOrDigit(s.charAt(lo))) lo++;
while (lo < hi && !Character.isLetterOrDigit(s.charAt(hi))) hi--;
if (Character.toLowerCase(s.charAt(lo)) != Character.toLowerCase(s.charAt(hi)))
return false;
lo++; hi--;
}
return true;
}
}
- Time Complexity: O(N)
- Space Complexity: O(1)