680. Valid Palindrome II

 一刷 2020/05

Runtime: 10 ms, faster than 58.06% of Java online submissions for Valid Palindrome II.

Memory Usage: 54.7 MB, less than 42.39% of Java online submissions for Valid Palindrome II.

class Solution {

    public boolean validPalindrome(String s) {

        // Use two pointers scan towards each other

        // If the pointed characters are not equal, check if there's any remaining quota left to delete character

        // If yes, try to move each pointer to skip one character and check the remaining string

        if (s == null || s.equals("")) {

            return true;

        }

        int left = 0, right = s.length() - 1;

        int delete = 1;

        return validPalinHelper(s, left, right, delete);

    }

    

    private boolean validPalinHelper(String s, int left, int right, int delete) {

        while (left < right) {

            if (s.charAt(left) == s.charAt(right)) {

                left++;

                right--;

                continue;

            }

            if (delete <= 0) {

                return false;

            }

            return validPalinHelper(s, left  + 1, right, delete - 1) || validPalinHelper(s, left, right - 1, delete - 1);

        }

        return true;

    }

}