glmapper

每天一道算法题:最长回文子串

字数统计: 602阅读时长: 2 min
2018/11/10 Share

##题目
给定一个字符串 s,找到 s 中最长的回文子串。你可以假设 s 长度最长为1000。

示例:

1
2
3
4
5
输入: "babad"

输出: "bab"

注意: "aba"也是有效答案

示例:

1
2
3
输入: "cbbd"

输出: "bb"

思路

一开始是想用最笨的方法来解的,也就是找出所有的字串,然后再对所有的子串进行回文检测,并记录长度。这种方式时间复杂度可想而知,O(n)O(n)O(n)=O(n^3)。所以这种肯定是不能满足我们要求的。

ok,那我们来分析一下这个问题,先把这个问题特殊化;

  • 假如输入的字符串长度就是1

    那么这个字符串的最长回文串就是它自己,长度就是1

  • 假如字符串长度为2,它要是回文串的化,就需要两个字符是相等的。

    即:s[i] == s[j] 且i-j=1(此处假定i是较大索引位置)

  • 那么对于i-j>1的情况下呢?是不是只要满足下面的条件就可以了:

    即:s[i] == s[j]&&s[i-1] == s[j+1]

其实这种思路就是动态规划。关于动态规划的理论性文字就不码了,有兴趣的小伙伴阔以自行学习。下面就针对这个问题码一下代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
public String longestPalindrome(String s) {
// 长度为1,返回当前串
if (s.length()==1){
return s;
}
//长度为2并且两个字符相等则返回
if (s.length()==2&&s.charAt(0)==s.charAt(1)){
return s;
}
//用于标记isLongestPalindrome[j][i]即从j到i是否是回文串;
//如isLongestPalindrome[1][5]==true则表示字符串索引位置从1到5的子串是回文串。
boolean[][] isLongestPalindrome = new boolean[s.length()][s.length()];
//最长回文串初始最大为0
int maxlen = 0;
//对应的maxlen的开始索引位置
int beginIndex = 0;
//对应的maxlen的结束索引位置
int lastIndex = 0;
for (int i=0;i<s.length();i++){
int j=i;
while(j>=0){
//满足上述的第三个条件,即当前s.charAt(i)==s.charAt(j)并
//且s[j+1到i-1]也是回文串
if (s.charAt(i)==s.charAt(j)&&(i-j<2||isLongestPalindrome[j+1][i-1])){
isLongestPalindrome[j][i]=true;
if (maxlen < i-j+1) {
beginIndex = j;
lastIndex = i+1;
maxlen = i-j+1;
}
}
j--;
}
}

return s.substring(beginIndex,lastIndex);
}

原文作者:GuoLei Song

原文链接:http://www.glmapper.com/2018/11/10/leetcode3/

发表日期:November 10th 2018, 1:33:24 pm

更新日期:November 10th 2018, 1:34:39 pm

版权声明:转载请注明出处

CATALOG
  1. 1. 思路