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

Example 1:

Input: s = "aba"
Output: true
Explanation: Originally a palindrome.

Example 2:

Input: s = "abca"
Output: true
Explanation: Delete 'b' or 'c'.

Example 3:

Input: s = "abc"
Output: false
Explanation: Deleting any letter can not make it a palindrome.

Notice

1. The string will only contain lowercase characters.
2. The maximum length of the string is 50000.

思路：看不相等的地方，去掉i或者j之后，是否是palindrome；

public class Solution {
    /**
     * @param s: a string
     * @return boolean: whether you can make s a palindrome by deleting at most one character
     */
    public boolean validPalindrome(String s) {
        if(s == null || s.length() == 0) {
            return true;
        }
        int i = 0; int j = s.length() -1;
        while(i <= j) {
            if(s.charAt(i) != s.charAt(j)){
                return isPalindrome(s.substring(i, j)) || isPalindrome(s.substring(i+1,j+1));
            }
            i++;
            j--;
        }
        return true;
    }
    
    private boolean isPalindrome(String s) {
        int i = 0; int j = s.length() - 1;
        while(i <= j) {
            if(s.charAt(i) != s.charAt(j)){
                return false;
            }
            i++;
            j--;
        }
        return true;
    }
}