Java O(n) Time O(1) Space


  • 8
    public boolean validPalindrome(String s) {
        int l = -1, r = s.length();
        while (++l < --r) 
            if (s.charAt(l) != s.charAt(r)) return isPalindromic(s, l, r+1) || isPalindromic(s, l-1, r);
        return true;
    }
    
    public boolean isPalindromic(String s, int l, int r) {
        while (++l < --r) 
            if (s.charAt(l) != s.charAt(r)) return false;
        return true;
    }
    

  • 2
    T

    Quite a similar solution from me

    class Solution {
        public boolean validPalindrome(String s) {
            int l=0;
            int r=s.length()-1;
            while(l<r){
                if(s.charAt(l)!=s.charAt(r)){
                    return isPalindrome(s,l+1,r) || isPalindrome(s,l,r-1);
                }
                ++l;
                --r;
            }
            return true;
        }
        public boolean isPalindrome(String s,int l,int r){
            while(l<r){
                if(s.charAt(l)==s.charAt(r)){
                    ++l;
                    --r;
                }
                else
                    return false;
            }
            return true;
        }
    }
    

  • 0
    C

    Wow, how simple I totally over engineered this problem. Nice solution.


  • 0

    Awesome!

    One line (line 2, 3) of the while() loop and the variables initialized above could be saved:

    for (int l = -1, r = s.length(); ++l < --r;)
        if (s.charAt(l) != s.charAt(r)) return isPalindromic(s, l, r + 1) || isPalindromic(s, l - 1, r);
    

    instead of

    int l = -1, r = s.length();
        while (++l < --r) 
            if (s.charAt(l) != s.charAt(r)) return isPalindromic(s, l, r+1) || isPalindromic(s, l-1, r);
    
    

  • 0
    S

    @compton_scatter

    Can you explain the reason behind writing the return statement logic in validPalindrome()
    line:4

    According to me it should be as follows
    return isPalindrome(s, i+1, j) || isPalindrome(s, i, j-1); either I will delete ith element or jth element from string.


  • 0

    @swapnilgupta This is because in the isPalindromic method, I immediately increment l and decrement r prior to entering the loop.


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.