Concise Java solution that beats 98.5%


  • 0
    C

    The main idea is to introduce a boolean that indicates if we have used that one chance of deletion. When we encounter two different characters, if already deleted, return false, else call function again for the two potential sub-problems. I believe this is O(n) space since I turned string into a char array, but that can be easily changed to O(1) space.

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

    Please correct me if you see anything inaccurate.


Log in to reply
 

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