Java, 7 lines solution, Two Pointers Technique, O(n) time complexity


  • 0
    C

    The basic idea is to use two pointers left and right to iterate through the String s, the first time we encounter different characters, we skip it by using isValid(s, left - 1, right, 1) | isValid(s, left, right + 1, 1).
    e.g.:

    ...  a     b    ...   a    b   ...
        left                  right
    

    We either compare (left, right - 1) or (left + 1, right) next time.

    If it is the second time we find differences, just return false, coz in this case, it is not possible to get a palindrome by only removing one character. Otherwise, return true.

        public boolean validPalindrome(String s) {
            
            return isValid(s, -1, s.length(), 0);
        }
        
        private boolean isValid(String s, int left, int right, int count) {
            
            while ( ++ left <= -- right) 
                if (s.charAt(left) != s.charAt(right)) {
                    if (count == 1) return false;
                    return isValid(s, left - 1, right, 1) | isValid(s, left, right + 1, 1);
                }
            
            return true;
        }
    

Log in to reply
 

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