echo

任生命穿梭 时间的角落

0%

最长回文子串

Posted on In Valine:

5. 最长回文子串

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

示例 1：

1
2
3
输入: "babad"
输出: "bab"
注意: "aba" 也是一个有效答案。

示例 2：

1
2
输入: "cbbd"
输出: "bb"

在看这个问题之前我们首先来看看如何判断回文字符串，我们很容易写出下面的代码。

1
2
3
4
5
6
7
8
boolean isPalindrome(String s){
	for(int i=0, j=s.length()-1; i<j; ++i,--j){
		if(s.charAt(i) != s.charAt(j)){
		return false;
		}
	}
	return true;
}

可以看出，回文字符串是关于一个字符或者最中心的两个字符左右对称的。

  • 当字符串中字符数为奇数时关于最中心的字符对称，例如 abcba 关于字符 c 对称。
  • 当字符串中字符数为偶数时关于最中心的两个字符之间的空格对称，例如 abba 关于 bb 对称。

一个字符数为 n 的字符串可以关于 n 个单字符对称，关于 n-1 个两个字符对称。我们只需遍历 2n - 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
class Solution {
public String longestPalindrome(String s) {
    if(s == null || s.length()<1)return "";
    int start=0, end=0;
    for(int i=0; i<s.length(); ++i){
        //关于单个字符对称
       int len1 = expandAround(s,i,i);
        //关于中心两个字符对称
       int len2 = expandAround(s,i,i+1);
        //取最大长度
       int len = Math.max(len1,len2);
        //记录最长回文子串的起始位置
       if(len > end-start){
       start = i - (len-1)/2;
        end = i + len/2;
       }

    }
    //返回子串
    return s.substring(start,end+1);
}
/*
* 求字符串 s 中，left right 开始的对称点的回文字符串长度。
* 当 left == right 时，关于单个字符对称，当 left + 1 == right 时关于s[left],s[right]这两个中心字* 符对称。
*/
private int expandAround(String s, int left, int right){
    while(left >=0 && right<s.length() && s.charAt(left) == s.charAt(right)){
        left--;
        right++;
    }

    return right-left-1;
}
}

时间复杂度 O(n^2)，空间复杂度O(1)。