680. Valid Palindrome II【easy】

680. Valid Palindrome II【easy】

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.

错误解法：

class Solution {
public:
    bool validPalindrome(string s) {
        int start = 0;
        int end = s.length() - 1;
        int flag = false;
        
        while (start <= end) {
            if (s[start] == s[end]) {
                ++start;
                --end;
            }
            else {
                if (!flag) {
                    flag = true;
                    
                    if (s[start + 1] == s[end]) {
                        ++start;
                    } else if (s[start] == s[end - 1]) {
                        --end;
                    } else {
                        return false;
                    } 
                } 
                else {
                    return false;
                }
            }
        }
        
        return true;
        
    }
};

没有通过以下测试用例：

"aguokepatgbnvfqmgmlcupuufxoohdfpgjdmysgvhmvffcnqxjjxqncffvmhvgsymdjgpfdhooxfuupuculmgmqfvnbgtapekouga"

考察代码逻辑，发现一开始我们命中了

s[start + 1] == s[end]

这个逻辑，"aguokepatgbnvfqmgmlcupuufxoohdfpgjdmysgvhmvffcnqxjjxqncffvmhvgsymdjgpfdhooxfuupuculmgmqfvnbgtapekouga"，并且设置了标志位，这就坑了，下次发现不相等的情况，就直接返回false了。

其实我们本意是要命中下面的逻辑

s[start] == s[end - 1]

"aguokepatgbnvfqmgmlcupuufxoohdfpgjdmysgvhmvffcnqxjjxqncffvmhvgsymdjgpfdhooxfuupuculmgmqfvnbgtapekouga"，并且设置了标志位，这样就可以满足测试用例。

就是说每次我们用

s[start + 1] == s[end]

和

s[start] == s[end - 1]

其实是一种“或”的关系，所以我们要一判断就判断到底，比如下面的解法一。

解法一：

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

        while (left < right)
        {
            if (s.charAt(left) == s.charAt(right))
            {
                left++; right--;
            }
            else
            {
                //remove right
                int templeft = left, tempright = right - 1;

                while (templeft < tempright)
                {
                    if (s.charAt(templeft) != s.charAt(tempright)) break;
                    templeft++; tempright--;

                    if (templeft >= tempright) return true;
                }

                //remove left
                left++;

                while (left < right)
                {
                    if (s.charAt(left) != s.charAt(right)) return false;
                    left++; right--;
                }
            }
        }
        return true;
    }
}

参考@yashar 的代码。

解法二：

class Solution {
    public boolean validPalindrome(String s) 
    {
        return validPalindrome(s, 0, s.length() - 1, false);
    }
    
    private boolean validPalindrome(String s, int left, int right, Boolean mismatch)
    {
        if (right < left) return true;

        if (s.charAt(left) != s.charAt(right))
        {
            if (mismatch == true)
                return false;

            return validPalindrome(s, left, right - 1, true) || validPalindrome(s, left + 1, right, true);
        }
        else
        {
            return validPalindrome(s, left + 1, right - 1, mismatch);
        }
    }
}

递归，参考@yashar 的代码。

解法三：

class Solution {
public:
    bool validPalindrome(string s) {
        return valid(s, 0, s.length() - 1, 1);
    }

private:
    bool valid(string& s, int i, int j, int d) { // d: num of chars you can delete at most
        if (i >= j) return true;
        if (s[i] == s[j])
            return valid(s, i + 1, j - 1, d);
        else
            return d > 0 && (valid(s, i + 1, j, d - 1) || valid(s, i, j - 1, d - 1));
    }
};

递归，参考@alexander 的代码。