验证回文串 II 图解题解

这道题到底在问什么

输入

s = "abcdeexdcba"

输出

true（删掉那个多出来的 'x'，剩下的串正反一样）

最优解：一步一步想明白

1. 3记住三件事：相等就往里收；第一次撞到不等时，分别试「删左」和「删右」；两条岔路有一条通，答案就是 true。下面每一帧都在套它。
2. 4开始：左指针 l 停在下标 0，右指针 r 停在最后一格。删除名额还留着，先按普通回文那样一对一对地比。
3. 5左边 'a' 和右边 'a' 一样，这一对配上了，可以放心往里收。
4. 6l 前进到下标 1、r 后退到下标 9，继续比下一对（绿色是已经确认相等的部分）。
5. 7左边 'b' 和右边 'b' 一样，这一对配上了，可以放心往里收。
6. 8l 前进到下标 2、r 后退到下标 8，继续比下一对（绿色是已经确认相等的部分）。
7. 9左边 'c' 和右边 'c' 一样，这一对配上了，可以放心往里收。
8. 10l 前进到下标 3、r 后退到下标 7，继续比下一对（绿色是已经确认相等的部分）。
9. 11左边 'd' 和右边 'd' 一样，这一对配上了，可以放心往里收。
10. 12l 前进到下标 4、r 后退到下标 6，继续比下一对（绿色是已经确认相等的部分）。
11. 13撞上了：左边 'e' 和右边 'x' 对不上（标红）。普通回文到这就失败了，但我们还有一次删除机会，下面分两条岔路试。
12. 14岔路一：假设删掉左边那个 'e'（标灰表示当它不存在），那么要比的就变成「下标 5 到 6」这一段，看它本身是不是回文。
13. 15删左这条路在 'e' 与 'x' 上又对不上了（这次没有删除名额可用了），所以「删左」走不通。
14. 16岔路二：换一种删法，假设删掉右边那个 'x'（标灰当它不存在），要比的就变成「下标 4 到 5」这一段，再看它是不是回文。
15. 17删右这条路上，'e' 和 'e' 相等，这一对配上了。
16. 18删右这段的指针交错而过，一路都相等。
17. 19删右这条路一路对上，剩下的部分是回文，删右可行——只要有一条岔路通，整体答案就成立。
18. 20结论：删掉那个对不上的 'x'，剩下的字符正读倒读完全一样，所以答案是 true。一次删除机会刚好用在了刀刃上。

⚠️ 容易写错的地方

完整代码（Python / C++ / Java）

def validPalindrome(s):
    def isPal(i, j):              # 普通回文判断
        while i < j:
            if s[i] != s[j]: return False
            i += 1; j -= 1
        return True
    l, r = 0, len(s) - 1
    while l < r:
        if s[l] != s[r]:         # 撞到不等：用掉删除名额
            return isPal(l + 1, r) or isPal(l, r - 1)
        l += 1; r -= 1
    return True

class Solution {
  bool isPal(const string& s, int i, int j){
    while (i < j){ if (s[i]!=s[j]) return false; i++; j--; }
    return true;
  }
public:
  bool validPalindrome(string s){
    int l = 0, r = s.size() - 1;
    while (l < r){
      if (s[l] != s[r])
        return isPal(s, l+1, r) || isPal(s, l, r-1);
      l++; r--;
    }
    return true;
  }
};

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

复杂度

面试官可能追问