[LeetCode]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:

<b>Input:</b> "aba"
<b>Output:</b> True

Example 2:

<b>Input:</b> "abca"
<b>Output:</b> True
<b>Explanation:</b> 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.

思路

水题。

判断是否是回文字符串最简单的方式就是从左右两端逐步向中心逼近（双指针），如下代码：

for (int i = 0; i < s.length(); ++i) {
    if (s[i] != s[s.length() - 1 - i]) return false;
}
return true;

题中指出可以最多删除一个字段，那么当遇到左右不一致时会有两个分支产生。即删除左边的字符，或者删除右边的字符。然后分别判断产生的两个子字符串是否是回文字符串即可。

代码

class Solution {
public:
    bool isValid(string s, int start, int end) {
        for (int i = start; i < (end - start + 1) / 2 + start; ++i) {
            if (s[i] != s[end - (i - start)]) return false;
        }
        return true;
    }
    bool validPalindrome(string s) {
        for (int i = 0; i < s.length() / 2; ++i) {
            if (s[i] != s[s.length() - i - 1]) {
                if (!isValid(s, i + 1, s.length() - i - 1) && !isValid(s, i, s.length() - i -2)) return false;
                break;
            }
        }
        return true;
    }
};

复杂度

时间复杂度：O(n)

空间复杂度：O(n)

技巧

• 由于只有两个分支，所以没有必要利用栈来实现回溯法。
• 再产生两个子字符串时，可以使用两个指针来指定子字符串的范围，而不是使用substr来分隔，并产生一些拷贝。