LeetCode 680 - Valid Palindrome II

https://leetcode.com/problems/valid-palindrome-ii/description/

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:

1. The string will only contain lowercase characters a-z. The maximum length of the string is 50000.

https://www.cnblogs.com/grandyang/p/7618468.html
这道题是之前那道Valid Palindrome的拓展，还是让我们验证回复字符串，但是区别是这道题的字符串中只含有小写字母，而且这道题允许删除一个字符，那么当遇到不匹配的时候，我们到底是删除左边的字符，还是右边的字符呢，我们的做法是两种情况都要算一遍，只要有一种能返回true，那么结果就返回true。我们可以写一个子函数来判断字符串中的某一个范围内的子字符串是否为回文串

X. Greedy

If the beginning and end characters of a string are the same (ie. s[0] == s[s.length - 1]), then whether the inner characters are a palindrome (s[1], s[2], ..., s[s.length - 2]) uniquely determines whether the entire string is a palindrome.

Algorithm

Suppose we want to know whether s[i], s[i+1], ..., s[j] form a palindrome. If i >= j then we are done. If s[i] == s[j] then we may take i++; j--. Otherwise, the palindrome must be either s[i+1], s[i+2], ..., s[j] or s[i], s[i+1], ..., s[j-1], and we should check both cases.

    public boolean isPalindromeRange(String s, int i, int j) {

        for (int k = i; k <= i + (j - i) / 2; k++) {

            if (s.charAt(k) != s.charAt(j - k + i)) return false;

        }

        return true;

    }

    public boolean validPalindrome(String s) {

        for (int i = 0; i < s.length() / 2; i++) {

            if (s.charAt(i) != s.charAt(s.length() - 1 - i)) {

                int j = s.length() - 1 - i;

                return (isPalindromeRange(s, i+1, j) ||

                        isPalindromeRange(s, i, j-1));

            }

        }

        return true;

    }

public boolean validPalindrome(String s) {

char[] chs = s.toCharArray();

// BUG: ArrayIndexOutOfBoundsException not chs.length

Result result = checkValidPalindrome(chs, 0, chs.length - 1);

// case ab

// aba abba case

if (result.valid)

return true;

// a[i]!=a[j]

// abca

int i = result.start;

int j = result.end;

return checkValidPalindrome(chs, i + 1, j).valid || checkValidPalindrome(chs, i, j - 1).valid;

}

// aba

// precondition: start > 0 && end < chs.length - 1

public Result checkValidPalindrome(char[] chs, int start, int end) {

while (start < end) {

if (chs[start] == chs[end]) {

start++;

end--;

} else {

break;

}

}

return new Result(start, end, start >= end);

}

private static class Result {

private int start, end;

private boolean valid;

public Result(int start, int end, boolean valid) {

super();

this.start = start;

this.end = end;

this.valid = valid;

}

}

Check from left and right at the same time until the first different pair.
Now we have something like a****b, where a and b are different.
We need to delete either a or b to make it a palindrome
https://leetcode.com/problems/valid-palindrome-ii/discuss/107714/Java-solution-isPalindrome

Follow normal way (two pointers) to check if s is palindrome. When two chars are not equal, try to skip (pseudo delete) either left one or right one and continue checking.

    public boolean validPalindrome(String s) {
        int i = 0, j = s.length() - 1;
        while (i < j && s.charAt(i) == s.charAt(j)) {
            i++; j--;
        }

        if (i >= j) return true;

        if (isPalin(s, i + 1, j) || isPalin(s, i, j - 1)) return true;
        return false;
    }

    private boolean isPalin(String s, int i, int j) {
        while (i < j) {
            if (s.charAt(i) == s.charAt(j)) {
                i++; j--;
            }
            else return false;
        }
        return true;
    }

https://leetcode.com/problems/valid-palindrome-ii/discuss/107716/Java-O(n)-Time-O(1)-Space

public boolean validPalindrome(String s) {
    int l = -1, r = s.length();
    while (++l < --r) 
        if (s.charAt(l) != s.charAt(r)) return isPalindromic(s, l, r+1) || isPalindromic(s, l-1, r);
    return true;
}

public boolean isPalindromic(String s, int l, int r) {
    while (++l < --r) 
        if (s.charAt(l) != s.charAt(r)) return false;
    return true;
}

X.
https://leetcode.com/articles/valid-palindrome-ii/
Approach #1: Brute Force [Time Limit Exceeded]
For each index i in the given string, let's remove that character, then check if the resulting string is a palindrome. If it is, (or if the original string was a palindrome), then we'll return true

Time Complexity: $O(N^2)$ where $N$ is the length of the string. We do the following $N$ times: create a string of length $N$ and iterate over it.

  public boolean isPalindrome(CharSequence s) {

    for (int i = 0; i < s.length() / 2; i++) {

      if (s.charAt(i) != s.charAt(s.length() - 1 - i)) {

        return false;

      }

    }

    return true;

  }

  public boolean validPalindrome(String s) {

    StringBuilder sb = new StringBuilder(s);

    for (int i = 0; i < s.length(); i++) {

      char c = sb.charAt(i);

      sb.deleteCharAt(i);

      if (isPalindrome(sb))

        return true;

      sb.insert(i, c);

    }

    return isPalindrome(s);

  }