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)