680. Valid Palindrome II

Given a non-empty string s, you may delete at most one character. Judge whether you can make it a palindrome.

Example 1:
Input: "aba"
Output: True
Example 2:
Input: "abca"
Output: True
Explanation: You could delete the character 'c'.
Note:
The string will only contain lowercase characters a-z. The maximum length of the string is 50000.

Solution

如果s[i] != s[j]时,check s[i, j - 1] || s[i + 1, j]是否为Palindrome

Complexity

O(N) O(1)

Code

class Solution {
    public boolean validPalindrome(String s) {
        if(s == null || s.length() == 0)
            return true;
        int l = 0, r = s.length() - 1;
        while(l < r){
            if(s.charAt(l) != s.charAt(r)){
                return isPalindrome(s, l, r - 1) || isPalindrome(s, l + 1, r);
            }
            l++;
            r--;
        }
        return true;
    }
    
    public boolean isPalindrome(String s, int l , int r){
        int i = l, j = r;
        while(i < j){
            if(s.charAt(i) != s.charAt(j))
                return false;
            i++;
            j--;
        }
        return true;
    }
}