LeetCode - 647. 回文子串
目录
题目
思路
步骤
字符串: "abcba"
中心点 i=0 (字符 'a')
中心点 i=1 (字符 'b')
中心点 i=2 (字符 'c')
中心点 i=3 (字符 'b')
中心点 i=4 (字符 'a')
总结计算
时间和空间复杂度
题目
647. 回文子串 - 力扣（LeetCode）
思路
中心扩展算法是寻找回文串的一种直观方法，基于以下观察：
- 每个回文串都有一个"中心"
- 从中心向两边扩展，如果两边字符相同，则形成更长的回文串
回文串的两种类型
奇数长度回文串：中心是单个字符
- 例如："aba" 中心是 'b'
- 扩展过程：'b' → 'aba'
偶数长度回文串：中心是两个相邻字符之间的位置
- 例如："abba" 中心是 'b' 和 'b' 之间
- 扩展过程：'bb' → 'abba'
步骤
遍历所有可能的中心点：
- 对于长度为n的字符串，共有2n-1个可能的中心点
- n个字符可以作为奇数长度回文串的中心
- n-1个字符间隙可以作为偶数长度回文串的中心
对每个中心点，尝试扩展：
- 从中心开始，向两边同时扩展
- 只要两边的字符相同，就继续扩展
- 每次成功扩展都找到一个新的回文子串
统计所有回文子串：
- 对所有中心点扩展的结果求和
过程
字符串: "abcba"
中心点 i=0 (字符 'a')
奇数长度扩展 (left=0, right=0):
[a] b c b a^- 'a' 是回文串，count=1
- 尝试扩展到 (-1,1)，左侧越界，停止
偶数长度扩展 (left=0, right=1):
a [b] c b a
^ ^- 'a'和'b'不同，不是回文串，count=0
中心点 i=1 (字符 'b')
奇数长度扩展 (left=1, right=1):
a [b] c b a^- 'b' 是回文串，count=1
- 尝试扩展到 (0,2
[a b c] b a^ ^- 'a'和'c'不同，不是回文串，停止
偶数长度扩展 (left=1, right=2):
a b [c] b a^ ^- 'b'和'c'不同，不是回文串，count=0
中心点 i=2 (字符 'c')
奇数长度扩展 (left=2, right=2):
a b [c] b a^- 'c' 是回文串，count=1
- 尝试扩展到 (1,3)
a [b c b] a^ ^- 'b'和'b'相同，是回文串，count=2
- 尝试扩展到 (0,4)
偶数长度扩展 (left=2, right=3):
a b c [b] a^ ^- 'c'和'b'不同，不是回文串，count=0
中心点 i=3 (字符 'b')
奇数长度扩展 (left=3, right=3):
a b c [b] a^- 'b' 是回文串，count=1
- 尝试扩展到 (2,4)
a b [c b a]^ ^- 'c'和'a'不同，不是回文串，停止
偶数长度扩展 (left=3, right=4):
a b c b [a]^ ^- 'b'和'a'不同，不是回文串，count=0
中心点 i=4 (字符 'a')
奇数长度扩展 (left=4, right=4):
a b c b [a]^- 'a' 是回文串，count=1
- 尝试扩展到 (3,5)，右侧越界，停止
偶数长度扩展 (left=4, right=5):
- 右侧越界，count=0
总结计算
总回文子串数量 = 1 + 0 + 1 + 0 + 3 + 0 + 1 + 0 + 1 + 0 = 7
这7个回文子串是:
- "a" (i=0)
- "b" (i=1)
- "c" (i=2)
- "bcb" (i=2)
- "abcba" (i=2)
- "b" (i=3)
- "a" (i=4)
时间和空间复杂度
- 时间复杂度: O(n²)
- 有 O(n) 个中心点
- 每个中心点最多扩展 O(n) 次
- 空间复杂度: O(1)
- 只使用了常数额外空间
正确写法
class Solution {
public:int countSubstrings(string s) {int result = 0;for(int i = 0; i<s.size();i++){result = result + dfs(s,i,i); //奇数的时候result = result + dfs(s,i,i+1); //偶数的时候}return result;}int dfs(string& s,int left, int right){int count = 0;while(left >= 0 && right <s.size() &&s[left] == s[right]){left--;right++;count++;}return count;}
};