AlgoPressAppearance
0005-最长回文子串
https://leetcode.cn/problems/longest-palindromic-substring
给你一个字符串 s，找到 s 中最长的回文子串。
示例 1：
输入：s = "babad"
输出："bab"
解释："aba" 同样是符合题意的答案。
示例 2：
输入：s = "cbbd"
输出："bb"
示例 3：
输入：s = "a"
输出："a"
示例 4：
输入：s = "ac"
输出："a"
提示：
1 <= s.length <= 1000
s 仅由数字和英文字母（大写和/或小写）组成
基本思路：双指针法
遍历字符串s，从 i 开始两边检测是否是回文，是的话，就扩展 l 和 r，如果超过当前回文串的长度就覆盖当前回文串 注意双位和单位的检测方法不一样, 双位 i,i+1 往两边扩展，单位 i-1,i+1往两边扩展
参考代码
csharp
public class Solution {
public string LongestPalindrome(string s) {
string pd = s[0].ToString();
int l,r;
//偶数回文
for(int i=0; i<s.Length-1; i++){
l = i;
r = i+1;
while(l>=0 && r<s.Length && s[l] == s[r]){
string newPd = s.Substring(l,r-l+1);
if(newPd.Length > pd.Length){
pd = newPd;
}
l--;
r++;
}
}
//奇数回文
for(int i=0; i<s.Length-1; i++){
l = i-1;
r = i+1;
//单位
while(l>=0 && r<s.Length && s[l] == s[r]){
string newPd = s.Substring(l,r-l+1);
if(newPd.Length > pd.Length){
pd = newPd;
}
l--;
r++;
}
}
return pd;
}
}
参考代码2：优化 偶数 和 奇数
csharp
public class Solution {
string pd;
private void ExpandCenter(int l, int r, string s){
while(l>=0 && r<s.Length && s[l] == s[r]){
string newPd = s.Substring(l,r-l+1);
if(newPd.Length > pd.Length){
pd = newPd;
}
l--;
r++;
}
}
public string LongestPalindrome(string s) {
pd = s[0].ToString();
//偶数
for(int i=0; i<s.Length-1; i++){
ExpandCenter(i,i+1,s);
}
//奇数
for(int i=0; i<s.Length-1; i++){
ExpandCenter(i-1,i+1,s);
}
return pd;
}
}
基本思路2： 动态规划
dp[i,j] 表示字符串s的第i到第j个字母组成的串是否为回文串 dp[i,j] = true 如果 s[i..j]是回文串，其他情况则是 false 如 s[i..j] 不是回文串，或者 i>j 此时 s[i..j]不合法
dp[i,j] = dp[i+1,j-1] ^ (s[i] == s[j]) 注意此处的 dp[i+1,j-1] 是往里面收缩 边界条件：dp[i,i] = true 单个字符自己就组成回文串， dp[i,i+1] = (s[i] == s[j]) 双数，就看两个是否相等
csharp
//TODO
public class Solution {
public string LongestPalindrome(string s) {
bool[,] dp = new bool[s.Length,s.Length];
//初始化边界
//length = 1
for(int i=0; i<s.Length; i++){
dp[i,i] = true;
}
int begin = 0;
int maxLength = 1;
for(int len = 2; len <= s.Length; len++){
for(int i=0; i<s.Length; i++){
int j = len + i -1;
if(j >= s.Length){
break;
}
if(s[i] == s[j]){
if(j - i < 3){ //2位或者3位
dp[i,j] = true;
}
else{
dp[i,j] = dp[i+1,j-1];
}
}
else{
dp[i,j] = false;
}
//统计当前长度
if(dp[i,j] && j - i +1 > maxLength){
maxLength = j-i+1;
begin = i;
}
}
}
return s.Substring(begin,maxLength);
}
}
复习：动态规划：20220615
csharp
public class Solution {
public string LongestPalindrome(string s) {
//动态规划
int n = s.Length;
bool[,] dp = new bool[n,n];
string result = "";
//状态转移
for(int i=n-1;i>=0;i--){
for(int j=i;j<n;j++){
if(j-i<=1){
dp[i,j] = s[i] == s[j];
}
else{
dp[i,j] = s[i] == s[j] && dp[i+1,j-1];
}
if(dp[i,j] && j-i+1 > result.Length){
result = s.Substring(i,j-i+1);
}
}
}
return result;
}
}