网络异常，图片无法展示
|
「这是我参与11月更文挑战的第12天，活动详情查看：2021最后一次更文挑战」
给你一个字符串 s ，请你统计并返回这个字符串中 回文子串 的数目。
回文字符串 是正着读和倒过来读一样的字符串。
子字符串 是字符串中的由连续字符组成的一个序列。
具有不同开始位置或结束位置的子串，即使是由相同的字符组成，也会被视作不同的子串。
示例 1：
输入： s = "abc" 输出： 3 解释： 三个回文子串: "a", "b", "c" 复制代码
示例 2：
输入： s = "aaa" 输出： 6 解释： 6个回文子串: "a", "a", "a", "aa", "aa", "aaa" 复制代码
提示：
1 <= s.length <= 1000s由小写英文字母组成
题解1
双层循环获取所有可能的子字符串，判断是否是回文字符串
如果是回文串，结果值 res++
代码如下：
/** * 校验给定字符串区间是否为回文串 * @param {string} s * @param {number} l * @param {number} r * @return {boolean} */ function check(s,l,r){ while(l<r){ if(s[l]!==s[r]) return false; else l++,r-- } return true; } var countSubstrings = function(s) { const len = s.length; // 因为每个字符可以是回文子串，所以初始化res为len let res = len; // 判断所有可能子串是否是回文串 for(let i = 0;i<len-1;i++){ for(let j = i+1;j<len;j++){ if(check(s,i,j)) res++ } } return res; }; 复制代码
以上题解提交通过后，耗时 320ms 左右，只击败了 17% 左右的用户
因为上述题解通过双层循环求得每一种子字符串，check 内层 check 函数又对该子字符进行判断是否为回文串，时间复杂度为 O(n³)
但是如果进行优化呢？
查找所有子字符串是一个必经的过程，这里只能是 O(n²) 的时间复杂度
校验每个子字符串是否是回文串，也只能是 O(n) 的时间复杂度
想了半天没有思路，于是厚着脸皮看了官方题解
网络异常，图片无法展示
|
题解2
官方直接跳过了获取所有子字符串的过程，直接通过中心拓展获取所有回文子串，那么中心拓展是如何做的呢？
- 首先会通过循环枚举所有可能的回文串的中心位置，然后判断当前左右位置的字符是否相等
- 如果相等，则结果值加一，左右指针继续向外拓展
- 如果不相等，则退出本次循环
代码如下：
var countSubstrings = function(s) { const n = s.length; let res = 0; // 枚举可能的回文串的中心位置，向左右扩展 // 如果相等，则找到新的回文串，res++ // 否则退出本次循环 for (let i = 0; i < 2 * n - 1; i++) { let l = i >> 1, r = (i >> 1) + i % 2; while (l >= 0 && r < n && s[l] == s[r]) { res++,l--,r++ } } return res; }; 复制代码
以上题解提交通过后，耗时 70ms 左右，击败了 90+% 用户
至此我们就完成了 leetcode-647-回文子串
如有任何问题或建议，欢迎留言讨论！
