Important links
- Problem: 125. Valid Palindrome
- Link to parent page: Two Pointer
- Java Cheat Sheet: link
Intuition
- Start with two points left and right.
- Keep moving towards center while checking if characters at left and right match
- If do not match, break (return false)
- If all characters match, return true at the end
Corner cases
- Check for lower/upper case (Convert whole string to lower)
- Check if a character is a letter of not
Solution
class Solution {
public boolean isPalindrome(String s) {
s = s.toLowerCase();
int left = 0, right = s.length() - 1;
while (left < right) {
tps(s, left, right);
if (!Character.isLetter(s.charAt(left))) {
left++;
continue;
}
if (!Character.isLetter(s.charAt(right))) {
right--;
continue;
}
if (s.charAt(left) != s.charAt(right)) {
return false;
}
left++;
right--;
}
return true;
}
private void tps(String s, int l, int r, String... prefix) {
if (prefix.length == 0) {
prefix = new String[] { "" };
}
System.out.print(prefix[0]);
for (int i = 0; i < s.length(); i++) {
if (i == l && i == r) {
System.out.printf("[(%s)]", s.charAt(i));
} else if (i == l) {
System.out.printf("(%s)", s.charAt(i));
} else if (i == r) {
System.out.printf("[%s]", s.charAt(i));
} else {
System.out.print(s.charAt(i));
}
System.out.printf(" ");
}
System.out.printf("| l=%s, r=%s %n", l, r);
}
}
Visualisation
I always use helper methods to print the two pointers and values at those points. This helps me visualize how the pointers are moving and debug if required.
Input: s="A man, a plan, a canal: Panama"
Std out:
(a) m a n , a p l a n , a c a n a l : p a n a m [a] | l=0, r=29
a ( ) m a n , a p l a n , a c a n a l : p a n a [m] a | l=1, r=28
a (m) a n , a p l a n , a c a n a l : p a n a [m] a | l=2, r=28
a m (a) n , a p l a n , a c a n a l : p a n [a] m a | l=3, r=27
a m a (n) , a p l a n , a c a n a l : p a [n] a m a | l=4, r=26
a m a n (,) a p l a n , a c a n a l : p [a] n a m a | l=5, r=25
a m a n , ( ) a p l a n , a c a n a l : p [a] n a m a | l=6, r=25
a m a n , (a) p l a n , a c a n a l : p [a] n a m a | l=7, r=25
a m a n , a ( ) p l a n , a c a n a l : [p] a n a m a | l=8, r=24
a m a n , a (p) l a n , a c a n a l : [p] a n a m a | l=9, r=24
a m a n , a p (l) a n , a c a n a l : [ ] p a n a m a | l=10, r=23
a m a n , a p (l) a n , a c a n a l [:] p a n a m a | l=10, r=22
a m a n , a p (l) a n , a c a n a [l] : p a n a m a | l=10, r=21
a m a n , a p l (a) n , a c a n [a] l : p a n a m a | l=11, r=20
a m a n , a p l a (n) , a c a [n] a l : p a n a m a | l=12, r=19
a m a n , a p l a n (,) a c [a] n a l : p a n a m a | l=13, r=18
a m a n , a p l a n , ( ) a c [a] n a l : p a n a m a | l=14, r=18
a m a n , a p l a n , (a) c [a] n a l : p a n a m a | l=15, r=18
a m a n , a p l a n , a ( ) [c] a n a l : p a n a m a | l=16, r=17
Top comments (0)