中心扩散法求最长回文子串
中心扩散法求字符串 s 中的回文串的最长子串时：
求当前字符串下标 i 的最长回文串思路步骤：
1.
1
2
3
4
5
| int left = i;
while (--left >= 0 && s.charAt(i) == s.charAt(left)) {
逻辑代码;
}
1234
|
2.
1
2
3
4
5
| int rigth = i;
while (++right < s.length() - 1 && s.charAt(i) == s.charAt(right)){
逻辑代码;
}
1234
|
3.
1
2
3
4
| while (--left > 0 && ++right < s.length() - 1 && s.charAt(left) == s.charAt(right)){
逻辑代码;
}
123
|
重复计算过多，可采取 dp 。 (虽然但是， dp写多了， 反而是想不到前面的中心扩散， 但弄完后， 前面的难度明显比 dp 难度低， 总而言之我是**)
1
2
3
4
5
6
7
8
| for (int i = 0; i < s.length(); i++) {
int left = i, right = i;
while (s.charAt(left) == s.charAt(right) && (right - left < 3 || dp[left + 1][right - 1])) {
dp[left][right] = true;
}
}
1234567
|
例题：
- 最长回文子串
给你一个字符串 s，找到 s 中最长的回文子串。
示例 1：
1
2
3
4
| 输入：s = "babad"
输出："bab"
解释："aba" 同样是符合题意的答案。
123
|
示例 2：
1
2
3
| 输入：s = "cbbd"
输出："bb"
12
|
题目来源：5. 最长回文子串 - 力扣（Leetcode）
参考题解：5. 最长回文子串 - 力扣（Leetcode）