# LeetCode：5_Longest Palindromic Substring | 最长的回文子串 | Medium

`Given a string S, find the longest palindromic substring in S. You may assume that the maximum length of S is 1000, and there exists one unique longest palindromic substring.`

2、动态规划法：（一般含“最XX”等优化词义的题意味着都可以动态规划求解），时间复杂度O(n^2)，空间复杂度O(n^2)。

dp[i][j] = dp[i+1][j-1] && s[i] == s[j]

``` 1 //动态规划法
2 string LongestPalindromicStringDP(string str)
3 {
4     size_t n = str.size();
5     if (n == 0 || n == 1)
6         return str;
7     //创建dp二维数组
8     //d[i][j] = dp[i+1][j-1] && s[i] == s[j]
9     bool **dp = new bool *[n];
10     for (size_t i = 0; i < n; ++ i)
11         dp[i] = new bool[n];
12
13     int nLongestIndex = 0; //最长回文子串的开始下标
14     int nMaxLen = 0; //长度
15
16     for (size_t i = 0; i < n; i ++)
17         for (size_t j = 0; j < n; j ++)
18             dp[i][j] = false;
19     for (size_t i = 0; i < n; ++ i)
20         dp[i][i] = true; //初始化一个字母
21
22     for (size_t i = 0; i < n - 1; ++ i) {
23         if (str[i] == str[i+1]) {
24             dp[i][i+1] = true; //初始化两个相同的字母"aa"
25             nLongestIndex = i;
26             nMaxLen = 2;
27         }
28     }
29     //从长度3开始操作, (aba)ba, a(bab)a, ab(aba)
30     for (size_t len = 3; len <= n; ++ len) {
31         for (size_t i = 0; i < n-len+1; ++ i) {
32             size_t j = i + len - 1;
33             if (str[i] == str[j] && dp[i+1][j-1]){
34                 dp[i][j] = true;
35                 nLongestIndex = i;
36                 nMaxLen = len;
37             }
38         }
39     }
40
41     //释放dp
42     for (size_t i = 0; i < n; ++ i)
43         delete []dp[i];
44     delete []dp;
45
46     return str.substr(nLongestIndex, nMaxLen);
47 }```

3、中心扩散法：时间复杂度O(n^2)，空间复杂度O(1) 顾名思义，从一个节点，分别向两边扩散，用两个指针分别向前向后遍历。

``` 1 //中心扩散法
2 string LongestPalindromicString(string str)
3 {
4     size_t n = str.size();
5     if (n == 0 || n == 1)
6         return str;
7
8     size_t start = 0;
9     size_t nMaxLen = 0;
10
11     for (size_t i = 0; i < n; ++ i) {
12         size_t j = i, k = i; //分别从中心向两边扩散
13         while(k < n-1 && str[k] == str[k+1])
14             k++; //有相同字母的情况："aaa"
15         while(j > 0 && k < n-1 && str[j-1] == str[k+1]){
16             k++; //不同字母情况: "aba"
17             j--;
18         }
19         if(k-j+1 > nMaxLen){
20             nMaxLen = k-j+1;
21             start = j;
22         }
23     }
24     return str.substr(start, nMaxLen);
25 }```

4、很明显，这两种方法时间复杂度还是太高了，还有一种算法叫Manacher，时间复杂度能够降为O(n)，空间复杂度也为O(n)，先记下，以后再做研究吧。

177 篇文章60 人订阅

0 条评论

## 相关文章

18040

33820

### BFPRT算法

首先将原数组分成5个一组，每组内进行排序，组间不排序，然后将每组的中位数取出再次进行上述操作，直到最后只能分成一组了，然后取出中位数，将这个中位数当作标尺进行...

11620

### 《编程之美》读书笔记（一）——中国象棋将帅有效位置

《编程之美》读书笔记（一） ——中国象棋将帅有效位置 （原创内容，转载请注明来源，谢谢） 一、问题 ? 如上述棋盘，假设将为点A，帅为点B。将只能在d10...

42360

10810

9120

9130

39470

31680

35250