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.

解题思路: 1、简单思路:暴力破解法,时间复杂度O(n^3),肯定通不过。

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

形如"abba", "abbba"这样的字符串,如果用dp[i][j]表示从下标i到j之间的子字符串所构成的回文子串的长度,则有:

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

初始化:

奇数个字符:dp[i][i] = 1; 偶数个字符:dp[i][i+1] = 1

 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),先记下,以后再做研究吧。

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏追不上乌龟的兔子

[多少懂点位运算】续·一行代码解决LeetCode268缺失数字

给定一个包含 0, 1, 2, ..., n 中 n 个数的序列,找出 0 .. n 中没有出现在序列中的那个数。

18040
来自专栏Leetcode名企之路

【Leetcode】60. 第k个排列

给定 n 的范围是 [1, 9]。 给定 k 的范围是[1, n!]。 示例 1:

33820
来自专栏mathor

BFPRT算法

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

11620
来自专栏决胜机器学习

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

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

42360
来自专栏小二的折腾日记

牛客网刷题总结-剑指offer(1)

这里一般的思路肯定是,从行或者列开始找,根据递增的顺序,找到行或者列之后再判断列或者行,知道找到为止。最好的方法是,从左下角或者右上角开始找。原因是:这样的一行...

10810
来自专栏desperate633

[编程题] 制造回文分析代码

我们知道回文串的话,就是前后相等,那么一个字符至少出现两次,除了一种情况,就是可以有一个字符只出现一次,就是这个字符在中间。 所以,我们的思路就是统计出现奇数...

9120
来自专栏ACM算法日常

独角兽与数列(置换群循环)- HDU 4985

群论是法国数学家伽罗瓦(Galois)的发明。伽罗瓦是一个极具传奇性的人物,年仅21岁就英年早逝于一场近乎自杀的决斗中。他用该理论,具体来说是伽罗瓦群,解决了五...

9130
来自专栏大数据学习笔记

Java程序设计(Java9版):第3章 流程控制

第3章 流程控制 学习要点 掌握三种流程控制 掌握简单的输入输出 了解三种循环设计方法 掌握数组、字符串和枚举类型 3.1 面向过程介绍...

39470
来自专栏python读书笔记

《python算法教程》Day3 - 递归递归简介代码示例

这是《python算法教程》的第3篇读书笔记。由于之前看书的效率太低了,所以拖了一个多星期才写第三篇读书笔记。这次主要简单总结一下递归(recursion)。 ...

31680
来自专栏我是攻城师

使用位运算替代模运算

35250

扫码关注云+社区

领取腾讯云代金券