125. Valid Palindrome

#twopointer #java

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