最长回文子串-526互联

题目：

给你一个字符串 s，找到 s 中最长的回文子串。

如果字符串的反序与原始字符串相同，则该字符串称为回文字符串。

示例 1：

输入：s = "babad"
输出："bab"
解释："aba" 同样是符合题意的答案。

示例 2：

输入：s = "cbbd"
输出："bb"

提示：

1 <= s.length <= 1000
s 仅由数字和英文字母组成

解法：动态规划

思路：

首先定义P(i,j)

P(i,j)=true s[i,j]是回文子串

P(i,j)=false s[i,j]不是回文子串

那么

P(i,j)=(P(i+1,j-1)&&s[i]==s[j])

如果 S[i+1,j−1] 是回文串，那么只要 S[i]== S[j]，就可以确定 S[i,j]也是回文串了。

按照这种思路，代码如下

 1 public class Solution {
 2     public string LongestPalindrome(string s) {
 3         if(s.Length<=1)
 4         {
 5             return s;
 6         }
 7         if(s.Length==2)
 8         {
 9             if(s[0]==s[1])
10             {
11                 return s;
12             }
13             else
14             {
15                 return s[0].ToString();
16             }
17         }
18         int length=s.Length;
19         bool[,] P = new bool[length,length];
20         int maxLen=0;
21         string maxStr="";
22         for(int len=1;len<=length;len++)
23         {
24             for(int start=0;start<length;start++)
25             {
26                 int end=start+len-1;
27                 if(end>=length)
28                 {
29                     break;
30                 }
31                 P[start,end]=((len==1||len==2||P[start+1,end-1])&&s[start]==s[end]);
32                 if(P[start,end]&&len>maxLen)
33                 {
34                     maxStr = s.Substring(start, end + 1-start);
35                 }
36             }
37         }
38         return maxStr;
39     }
40 }