Java O(n) Time O(1) Space


  • 14
    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;
    }
    

  • 3
    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;
        }
    }
    

  • 1
    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.


  • 0
    S

    Similar idea, but without defining another method (Not a good idea)

    class Solution {
        boolean found = false;
        public boolean validPalindrome(String s) {
            
            int i = 0, j = s.length() - 1;
            
            while( i++ < j-- ) {
                // System.out.println(s.charAt(i) +" -> "+ s.charAt(j));
                if( s.charAt(i) != s.charAt(j)) {
                    if(found) return false;
                    found = true;
                    return validPalindrome(s.substring(i+1, j+1)) || validPalindrome(s.substring(i, j));
                } 
            }
            return true;
        }
    }
    

  • 2

    without fancy code.

        public boolean validPalindrome(String s) {
          char[] sc = s.toCharArray();
          int i = 0, j = s.length() - 1;
          while(i < j){
            if(sc[i] != sc[j]){
              return helper(sc, i + 1, j) || helper(sc, i, j - 1);
            }
            i++;
            j--;
          }
            return true;
        }
    
        boolean helper(char[] sc, int i, int j){
           while(i < j){
             if(sc[i] != sc[j]) return false;
             i++; j--;
           }
          return true;
        }

  • 0

    Excellent solution, it is all about the idea!


Log in to reply
 

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