680. Valid Palindrome II

JIAKAOBO

LeetCode

感谢赞助!

• ㊗️
• 大家
• offer
• 多多！

Problem

Given a string s, return true if the s can be palindrome after deleting at most one character from it.

Example 1:

Input: s = "aba"
Output: true

Example 2:

Input: s = "abca"
Output: true
Explanation: You could delete the character 'c'.

Example 3:

Input: s = "abc"
Output: false

Constraints:

• $1 <= s.length <= 10^5$
• s consists of lowercase English letters.

Code

class Solution {
    public boolean validPalindrome(String s) {
        int left = 0;
        int right = s.length() - 1;

        while (left < right) {
            char x = s.charAt(left);
            char y = s.charAt(right);

            if (x == y) {
                left++;
                right--;
                continue;
            }

            return isPal(s, left + 1, right) || isPal(s, left, right - 1);
        }

        return true;
    }

    private boolean isPal(String s, int left, int right) {
        while (left < right) {
            char x = s.charAt(left);
            char y = s.charAt(right);
            if (x != y) return false;
            left++;
            right--;
        }

        return true;
    }
}