Two pointers
Valid Palindrome
- Problem: Given a string, determine if it is a palindrome, considering only alphanumeric characters and ignoring cases.
- Example:
Input: "A man, a plan, a canal: Panama".Output: true.
Two Pointers Approach:
- Initialize Two Pointers: One pointer (
left) starts at the beginning of the string, and the other (right) starts at the end. - Iterate and Compare:
- Ignore non-alphanumeric characters by moving the pointers inward.
- Compare characters at both pointers. If they are not equal (ignoring case), return false.
- Continue until the pointers meet or cross each other.
- If all comparisons are equal, return true.
Code
public boolean isPalindrome(String s) {
int left = 0; // Start of the string
int right = s.length() - 1; // End of the string
while (left < right) {
// Move the left pointer to the right if it's not an alphanumeric character
while (left < right && !Character.isLetterOrDigit(s.charAt(left))) {
left++;
}
// Move the right pointer to the left if it's not an alphanumeric character
while (left < right && !Character.isLetterOrDigit(s.charAt(right))) {
right--;
}
// Compare characters at both pointers ignoring case
if (Character.toLowerCase(s.charAt(left)) != Character.toLowerCase(s.charAt(right))) {
return false; // Not a palindrome
}
// Move both pointers towards the center
left++;
right--;
}
return true; // All characters matched
}
