Java O(n) Time O(1) Space


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


  • 1

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

  • 4

    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!


  • 1
    W

    Another Java variant of the same idea:

    class Solution {
        public boolean validPalindrome(String s) {
            return helper(s, 0, s.length() - 1, false);
        }
        
        private boolean helper(String s, int start, int end, boolean hasDeleted) {
            if (start >= end) return true;
            
            while (start < end) {
                if (s.charAt(start) != s.charAt(end)) {
                    if (hasDeleted) return false;
                    else return helper(s, start + 1, end, true) || helper(s, start, end - 1, true);
                }
                
                start++;
                end--;
            }
            return true;
        }
    }
    

  • 0
    J

    May I ask if the question requires adding one character to anywhere in a string, how to check whether the original string can be changed to a palindrome?


  • 0
    J

    @Jerry Hi, Jerry, May I ask if the question requires adding one character to anywhere in a string, how to check whether the original string can be changed to a palindrome?


  • 0

    My solution without helper function:

    class Solution {
        public boolean validPalindrome(String s) {
            if (s.length () <= 1)
                return true;
            char[] chs = s.toCharArray ();
            int lo = 0, hi = chs.length - 1;
            while (lo <= hi && chs[lo] == chs[hi]) {
                lo++;
                hi--;
            }
            // If all match, then finish
            if (lo > hi)
                return true;
            // LO2 represents the new LO if we skip [LO], and HI2 if we skip [HI]
            int lo2 = lo + 1, hi2 = hi - 1;
            // Will skipping [LO] make things work? 
            while (lo2 <= hi && chs[lo2] == chs[hi]) {
                lo2++;
                hi--;
            }
            if (lo2 > hi)
                return true;
            // Will skipping [HI] make things work?
            while (lo <= hi2 && chs[lo] == chs[hi2]) {
                lo++;
                hi2--;
            }
            if (lo > hi2)
                return true;
            // Doesn't work
            return false;
        }
    }
    

    click here for more information.


Log in to reply
 

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