回文判断

一句话理解

回文是正着读和倒着读一样。

为什么要学

字符串题的基本识别，后面区间 DP 也会再遇到。

讲解

两端指针 i、j，不断比较 s[i] 和 s[j]，相等就 i++、j—，直到相遇。有一处不同就不是回文。

空串和单字符都是回文。是否忽略大小写、空格，要看题目。

例子

bool pal(string s) {
    int i = 0, j = (int)s.size() - 1;
    while (i < j) {
        if (s[i] != s[j]) return false;
        i++; j--;
    }
    return true;
}

对 “aba”：比较 a 和 a，再剩下中间 b，成功。对 “ab”：a 和 b 不同，失败。

常见错误

• 空串时 j=-1 还去访问 s[j]。先处理长度。
• 比较时改了原串却还当原串用。