Leetcode 647. 回文子串【C++】

回文子串

给定一个字符串，你的任务是计算这个字符串中有多少个回文子串。

具有不同开始位置或结束位置的子串，即使是由相同的字符组成，也会被视作不同的子串。

示例 1：

输入："abc"
输出：3
解释：三个回文子串: "a", "b", "c"

示例 2：

输入："aaa"
输出：6
解释：6个回文子串: "a", "a", "a", "aa", "aa", "aaa"

提示：

输入的字符串长度不会超过 1000 。

解题思路

很容易知道单个字符也是回文串，所以任意长度的字符串至少有 s.length() 个回文子串，问题就可以转化为求长度大于1回文子串的个数。

回文串有两种情况，一种长度为奇数，一种长度为偶数，区别就在于正中心是单个字符（例如 'aba' ）还是两个相同的字符（例如 'abba' ），所以只要把这两种情况区别开来，然后以其为中心不断往两边扩展，实际上只要判断两侧对应位置上的字符是否相同即可，每多找到一个就+1，一旦遇到不相等字符则不可能有更大的回文子串了，所以跳出循环。

源码

class Solution {
public:
    int countSubstrings(string s) {
        int len = s.length();  // 字符串长度
        int count = len;
        for (int i = 0; i < len - 1; i++) {
            int c = 1;  // 用于往两边扩展判断
            //偶数回文串。下一个字符和当前字符相等
            if (s[i] == s[i + 1]) {
                count++;  // 回文子串'aa'
                // 往两边扩展判断
                while (i - c >= 0 && i + c + 1 < len)
                {
                    if (s[i - c] == s[i + c + 1]) count++;
                    else break;
                    c++;
                }
            }
            c = 1;
            //奇数回文串
            while (i - c >= 0 && i + c < len)
            {
                if (s[i - c] == s[i + c]) count++;
                else break;
                c++;
            }
        }
        return count;
    }
};