Sword finger offer II 019 Delete at most one character to get a palindrome

Summary

It's still two finger needling , And deleting at most one character is the key ！

subject

Given a non empty string s, Please judge if most If you delete a character from the string, you can get a palindrome string .

Ideas

Direct double pointer traverses from both ends to the middle , Compare the two characters for consistency . In the stem of the question Delete at most one character It's a key . If we encounter character inconsistencies , Do we delete the left pointer or the right pointer ？ Try both , See whether the substring formed after deleting two pointers is a palindrome string . If not , shows Delete at most one character It's impossible .

solution ： Double pointer + Determine whether the substring is a palindrome at one time

Code

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

    }
    return true;
}

public boolean isPalindrome(String s) {
    for (int i = 0; i <= s.length() / 2 - 1; i++) {
        if (s.charAt(i) != s.charAt(s.length() - i - 1)) {
            return false;
        }
    }
    return true;
}