DEV Community

Arpit Rathore
Arpit Rathore

Posted on

125. Valid Palindrome

Important links

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);
    }
}
Enter fullscreen mode Exit fullscreen mode

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
Enter fullscreen mode Exit fullscreen mode

Top comments (0)

Postmark Image

Speedy emails, satisfied customers

Are delayed transactional emails costing you user satisfaction? Postmark delivers your emails almost instantly, keeping your customers happy and connected.

Sign up