125. Valid Palindrome

• Important links
• Intuition
• Corner cases
• Solution
• Visualisation

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