Problem
Given a string s, return true if it is a palindrome after converting all uppercase letters to lowercase and removing all non-alphanumeric characters. Otherwise, return false.An empty string is considered a valid palindrome.
Example(s)
Consider the following example(s) to understand the expected input and output.Input
s = "A man, a plan, a canal: Panama" Output
trueSolution
This solution uses the Two Pointer technique. One pointer starts from the beginning of the string, while the other starts from the end.The left pointer skips non-alphanumeric characters, and the right pointer does the same from the opposite direction. The characters are then compared after converting them to lowercase.
If the characters do not match, the string is not a palindrome. Otherwise, both pointers move toward the center until they meet.
public boolean isPalindrome(String s) {
int left = 0;
int right = s.length() - 1;
while (left < right) {
while (left < right && !Character.isLetterOrDigit(s.charAt(left))) {
left++;
}
while (left < right && !Character.isLetterOrDigit(s.charAt(right))) {
right--;
}
if (Character.toLowerCase(s.charAt(left))
!= Character.toLowerCase(s.charAt(right))) {
return false;
}
left++;
right--;
}
return true;
}
Complexity
The algorithm traverses the string using two pointers, and each character is processed at most once, resulting in a time complexity ofO(n). The algorithm uses only two pointers and does not create another string, so the extra space complexity is
O(1).