《剑指 Offer》专项突破版 - 面试题 18、19 和 20 - 详解回文字符串（C++ 实现）

目录

前言

面试题 18 : 有效的回文

面试题 19 : 最多删除一个字符得到回文

面试题 20 : 回文子字符串的个数

前言

回文是一类特殊的字符串。不管是从头到尾读取一个回文，还是颠倒过来从尾到头读取一个回文，得到的内容是一样的。

英语中有很多回文单词，如 "noon" 和 "madam" 等。如果不考虑字符串中的空格和标点符合，并且忽略大小写的不同，那么还有更多有意思的回文，如 "Sir, I demand, I am a maid named Iris." 和 "Bob: Did Anna peep? Anna: Did Bob" 等。

中文博大精深，自然也有很多有趣的回文，如有回文对联 "上海自来水来自海上" 和 "黄山落叶松叶落山黄" 等。如果不考虑标点符号，中文还有 "我为人人，人人为我" 等经典回文。

面试题 18 : 有效的回文

题目：

给定一个字符串，请判断它是不是回文。假设只需要考虑字母和数字字符，并忽略大小写。例如，"Was it a cat I saw?" 是一个回文字符串，而 "race a car" 不是回文字符串。

分析：

判断一个字符串是不是回文，常用的方法就是使用双指针。可以定义两个指针，一个指针从第 1 个字符开始从前向后移动，另一个指针从最后一个字符开始从后向前移动。如果两个指针指向的字符相同，则同时移动这两个指针来判断它们指向的下一个字符是否相同。这样一直移动下去，直到两个指针相遇。

由于题目要求只考虑字母和数字字符，如果某个指针指向的字符既不是字母也不是数字，则移动指针跳过该字符。同时，题目要求忽略大小写，因此需要把所有的字母都转换成小写形式（或大写形式）再做比较。

代码实现：

class Solution {
public:
    bool isPalindrome(string s) {
        int left = 0, right = s.size() - 1;
        while (left < right)
        {
            while (left < right && isalnum(s[left]) == 0)
                ++left;
            
            while (left < right && isalnum(s[right]) == 0)
                --right;
            
            if (tolower(s[left]) != tolower(s[right]))
                return false;
            
            ++left;
            --right;
        }
        return true;
    }
};

面试题 19 : 最多删除一个字符得到回文

题目：

给定一个非空字符串 s，请判断如果最多从字符串中删除一个字符能不能得到一个回文字符串。

示例 1：

输入: s = "abca"
输出: true
解释: 可以删除 "c" 字符 或者 "b" 字符

示例 2：

输入: s = "abc"
输出: false

注意：

字符串 s 只包含小写英文字母。

分析：

和题目 3.1 类似，本题还是从字符串的两端开始向里逐步比较两个字符是不是相同。如果相同，则继续向里移动指针比较里面的两个字符。如果不相同，按照题目的要求，在删除一个字符之后再比较其他的字符就能够形成一个回文。由于事先不知道应该删除两个字符中的哪一个，因此两个字符都可以进行尝试。

代码实现：

class Solution {
public:
    bool isPalindrome(string s, int left, int right) {
        while (left < right)
        {
            if (s[left] != s[right])
                return false;
            
            ++left;
            --right;
        }
        return true;
    }
​
    bool validPalindrome(string s) {
        int left = 0, right = s.size() - 1;
        while (left < right)
        {
            if (s[left] != s[right])
                return isPalindrome(s, left + 1, right) || isPalindrome(s, left, right - 1);
            
            ++left;
            --right;
        }
        return true;
    }
};

面试题 20 : 回文子字符串的个数

题目：

给定一个字符串，请问该字符串中有多少个回文连续子字符串？例如，字符串 "abc" 有 3 个回文子字符串，分别为 "a"、"b" 和 "c"；而字符串 "aaa" 有 6 个回文子字符串，分别为 "a"、"a"、"a"、"aa"、"aa" 和 "aaa"。

注意：

字符串中只含小写英文字母。

分析：

前面都是从字符串的两端开始向里移动指针来判断字符串是否是一个回文，其实也可以换一个方向从字符串的中心开始向两端延伸。

如果存在一个长度为 m 的回文子字符串，则分别再向该回文的两端延伸一个字符，并判断回文前后的字符是否相同。如果相同，就找到一个长度为 m + 2 的回文子字符串。例如，在字符串 "abcba" 中，从中间的 "c" 出发向两端延伸一个字符，由于 "c" 前后都是字符 'b'，因此找到了一个长度为 3 的回文子字符串 "bcb"。然后向两端延伸一个字符，由于 "bcb" 的前后都是字符 ‘a’，因此又找到一个长度为 5 的回文子字符串 "abcba"。

值得注意的是，回文的长度既可以是奇数，也可以是偶数。长度为奇数的回文的对称中心只有一个字符，而长度为偶数的回文的对称中心有两个字符。

代码实现：

class Solution {
public:
    int countPalindrome(string s, int left, int right)
    {
        int count = 0;
        while (left >= 0 && right < s.size() && s[left] == s[right])
        {
            ++count;
            // 分别向回文的两端延伸一个字符
            --left;
            ++right;
        }
        return count;
    }
​
    int countSubstrings(string s) {
        int totalCount = 0;
        for (int i = 0; i < s.size(); ++i)
        {
            totalCount += countPalindrome(s, i, i);
            totalCount += countPalindrome(s, i, i + 1);
        }
        return totalCount;
    }
};

字符串的下标为 i。第 i 个字符本身可以成为长度为奇数的回文子字符串的对称中心，同时第 i 个字符和第 i + 1 个字符可以一起成为长度为偶数的回文子字符的对称中心。因此在上述代码中，for 循环通过对每个下标调用两次 countPalindrome 来统计回文子字符串的个数。

该解法的时间复杂度是 O(n^2)，空间复杂度是 O(1)。