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

本文最后更新于:2020年11月19日 上午

回文子串

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

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

示例 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;
    }
};