⭐️前面的话⭐️
本篇文章介绍有关回文字符串两道题题解，分别为【647. 回文子串
】和【 5. 最长回文子串】， 难度均为： 中等 标签： 双指针中心扩散 动态规划，展示语言java。
📒博客主页：未见花闻的博客主页
🎉欢迎关注🔎点赞👍收藏⭐️留言📝
📌本文由未见花闻原创，CSDN首发！
📆首发时间：🌴2022年10月12日🌴
✉️坚持和努力一定能换来诗与远方！
💭推荐书籍：📚《算法》，📚《算法导论》
💬参考在线编程网站：🌐牛客网🌐力扣
博主的码云gitee，平常博主写的程序代码都在里面。
博主的github，平常博主写的程序代码都在里面。
🍭作者水平很有限，如果发现错误，一定要及时告知作者哦！感谢感谢！
📌导航小助手📌
、
⭐️647. 回文子串⭐️
🔐题目详情
难度中等
给你一个字符串 s ，请你统计并返回这个字符串中 回文子串 的数目。
回文字符串 是正着读和倒过来读一样的字符串。
子字符串 是字符串中的由连续字符组成的一个序列。
具有不同开始位置或结束位置的子串，即使是由相同的字符组成，也会被视作不同的子串。
示例 1：
输入：s = "abc"
输出：3
解释：三个回文子串: "a", "b", "c"
示例 2：
输入：s = "aaa"
输出：6
解释：6个回文子串: "a", "a", "a", "aa", "aa", "aaa"
提示：
1 <= s.length <= 1000s由小写英文字母组成
💡解题思路
基本思路： 双指针
解题思路：
我们可以使用两个指针分别指向回文串中心的右边与左边，对于回文串，如果长度是偶数，那么中间的中心字符有两个，如果长度为奇数，那么中间的中心字符就是一个，下面我们以这两种情况对字符串进行单字符遍历和双字符遍历，以遍历到的字符作为中心进行回文子串的判断，并计数。
不妨设回文子串个数为ans，左指针left，右指针right。
情况1：单字符为中心，双指针向外扩散判断。
不妨设遍历到的字符下标为i，则初始left=i right=i，我们向两周扩散（即left-- right++），判断左右两个字符是否相等，如果相等表示有一个新的回文子串出现ans++，不相等或者下标不合法直接退出扩散验证，进行双字符为中心的判断。
情况2：双字符为中心，双指针向外扩散判断。
不妨设遍历到的字符下标为i，另一个中心字符下标为i+1，则初始left=i right=i+1，我们向两周扩散（即left-- right++），判断左右两个字符是否相等，如果相等表示有一个新的回文子串出现ans++，不相等或者下标不合法直接退出扩散验证，进入下一轮中心字符的验证。
🔑源代码
中心一个字符与两个字符扩散
class Solution {
public int countSubstrings(String s) {
char[] cs = s.toCharArray();
int n = cs.length;
int ans = 0;
//中心扩散
for (int i = 0; i < n; i++) {
//以一个字符为中心
int l = i;
int r = i;
while (l >= 0 && r < n && cs[l] == cs[r]) {
ans++;
l--;
r++;
}
//以两个字符为中心
l = i;
r = i + 1;
while (l >= 0 && r < n && cs[l] == cs[r]) {
ans++;
l--;
r++;
}
}
return ans;
}
}
🌱总结
⭐️5. 最长回文子串⭐️
🔐题目详情
难度中等
给你一个字符串 s，找到 s 中最长的回文子串。
示例 1：
输入：s = "babad"
输出："bab"
解释："aba" 同样是符合题意的答案。
示例 2：
输入：s = "cbbd"
输出："bb"
提示：
1 <= s.length <= 1000s仅由数字和英文字母组成
💡解题思路
基本思路： 双指针 动态规划
解题思路：
思路1： 双指针中心扩散，与前面一道题思路相同，前一题【647. 回文子串】我们运用了双指针中心扩散的方法进行解决，本题也可以使用该思路。
在【647】题中，求的是回文子串的总个数，而本题要求最长的回文子串，其实在【647】题基础上，我们统计一下每一次以单字符或双字符为中心验证的最长回文子串长度，并记录下所有中心扩散验证的最长回文字符串的长度和开始下标以及结束下标，最后得到最长的回文子串就是题目所求。
思路2： 动态规划
具体待补充。
🔑源代码
思路1：双指针，中心扩散
写法1：
class Solution {
public String longestPalindrome(String s) {
char[] cs = s.toCharArray();
int n = cs.length;
int ans = 0;
//中心扩散
int maxLen = 0;
int st = 0;
int en = 0;
for (int i = 0; i < n; i++) {
//以一个字符为中心
int l = i;
int r = i;
while (l >= 0 && r < n && cs[l] == cs[r]) {
ans++;
l--;
r++;
}
int len = r - l - 1;
if (len > maxLen) {
st = l + 1;
en = r - 1;
maxLen = len;
}
//以两个字符为中心
l = i;
r = i + 1;
while (l >= 0 && r < n && cs[l] == cs[r]) {
ans++;
l--;
r++;
}
len = r - l - 1;
if (len > maxLen) {
st = l + 1;
en = r - 1;
maxLen = len;
}
}
return s.substring(st, en + 1);
}
}
写法2：不用分别讨论单字符与双字符两种情况的验证，但会有重复判断，没有写法1效率高
class Solution {
public String longestPalindrome(String s) {
//中心扩散
char[] cs = s.toCharArray();
int n = cs.length;
int l = 0;
int r = 0;
int st = 0;
int en = 0;
int maxLen = 0;
for (int i = 0; i < n; i++) {
l = i - 1;
r = i + 1;
int len = 1;
//左
while (l > 0 && cs[l] == cs[i]) {
l--;
len++;
}
//右
while (r < n && cs[r] == cs[i]) {
r++;
len++;
}
//左手拉右手一起对着走
while (r < n && l >= 0 && cs[l] == cs[r]) {
l--;
r++;
len += 2;
}
if (len > maxLen) {
maxLen = len;
st = l + 1;
en = r - 1;
}
}
return s.substring(st, en + 1);
}
}
思路2：动态规划
class Solution {
public String longestPalindrome(String s) {
//动态规划
//状态定义 f[l][r]表示从l到r下标之间的字符串是否是回文串
//初始状态 l==r时 cs[r] == cs[l] && r - l <= 2时 f[l][r] = true
//转移方程 f[l][r] = f[l + 1][r - 1]
char[] cs = s.toCharArray();
int n = cs.length;
boolean[][] f = new boolean[n][n];
//记录开始下标 结束下标
int st = 0;
int en = 0;
int maxLen = 0;
for (int r = 1; r < n; r++) {
for (int l = r; l >= 0; l--) {
//初始化 l=r 或者 cs[r] == cs[l] 且 r - l <= 2 则f[l][r]为true
if (cs[r] == cs[l] && r - l <= 2) f[l][r] = true;
//如果cs[r] == cs[l] f[l][r] = f[l + 1][r - 1]
else if (cs[l] == cs[r]) f[l][r] = f[l + 1][r - 1];
//记录
int len = r - l + 1;
if (f[l][r] && len > maxLen) {
maxLen = len;
st = l;
en = r;
}
}
}
return s.substring(st, en + 1);
}
}
🌱总结
