LeetCode 5.最长的回文字符串

5. Longest Palindromic Substring

给定一个字符串s,找出其中最长的回文格式的子字符串。你可以假设长度的最大值为1000.

Example:

1
2
3
Input: "babad"
Output: "bab"

Note: “aba” is also a valid answer.

Example:

1
2
3
Input: "cbbd"
Output: "bb"

一开始以为palindrome是重复的意思,走了很大的弯路,后来才知道指的是回文格式,就是一个顺着读和反过来读都一样的字符串。
由此可知他有两种情况,一种是奇数的情况,中间的一个字符独立,其余的字符以中间为轴两两对应。另一种是偶数的情况,所有的字符都以中间为轴两两对应。

方法一:

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
public class Solution {
private int lo, maxLen;
public String longestPalindrome(String s) {
int len = s.length();
if (len < 2)
return s;
for (int i = 0; i < len - 1; i++) {
extendPalindrome(s, i, i); //assume odd length, try to extend Palindrome as possible
extendPalindrome(s, i, i + 1); //assume even length.
}
return s.substring(lo, lo + maxLen);
}
private void extendPalindrome(String s, int j, int k) {
while (j >= 0 && k < s.length() && s.charAt(j) == s.charAt(k)) {
j--;
k++;
}
if (maxLen < k - j - 1) {
lo = j + 1;
maxLen = k - j - 1;
}
}
}

效率

分析
这个方法分为奇偶两种情况进行计算。首先对每一个字符串里的字符进行两种情况的计算,extendPalindrome方法的原理就是当对应的位置的字符相同时,就将左侧字符向左一位,右侧字符向右一位,然后再重复进行这个比较过程。
时间复杂度 : O(n^2) 。n是字符串的长度
空间复杂度 : O(n) .

方法二:

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
public class Solution {
public String longestPalindrome(String s) {
String res = "";
int currLength = 0;
for(int i=0;i<s.length();i++){
if(isPalindrome(s,i-currLength-1,i)){
res = s.substring(i-currLength-1,i+1);
currLength = currLength+2;
}
else if(isPalindrome(s,i-currLength,i)){
res = s.substring(i-currLength,i+1);
currLength = currLength+1;
}
}
return res;
}
public boolean isPalindrome(String s, int begin, int end){
if(begin<0) return false;
while(begin<end){
if(s.charAt(begin++)!=s.charAt(end--)) return false;
}
return true;
}
}

效率

分析
这个方法主要是每当指针向右移时,我们都以这个位置的字符为结尾看是否能有新的长度为length(current length +1 或者 current length +2)的回文字符串。

时间复杂度 : O(n^2) 。n是字符串长度。
空间复杂度 : O(n) .

方法三 Manacher算法

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
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
public class Solution {
public String longestPalindrome(String s) {
char[] str = changeString(s);
String result = manacher(str,s);
return result;
}
/**
* 返回例如 #a#c#b#c#a#a#c#b#c#d#形式的字符串数组
*
* @param s
* @return
*/
public static char[] changeString(String s)
{
char[] str = new char[s.length() * 2 + 1];
int i = 0;
for (; i < s.length(); i++)
{
str[2 * i] = '#';
str[2 * i + 1] = s.charAt(i);
}
str[2 * i] = '#';
return str;
}
/**
* manacher 算法实现找到回文字符串最长的一个
*/
public static String manacher(char[] s,String olds)
{
String result = "";
int rad[] = new int[s.length];
int start = 0;
int end = 0;
//i index,j 回文半径,k
int i = 1, j = 0, k;
// 记录最长的回文串的长度
int maxLen = 0;
while (i < s.length)
{
// 扫描得出rad值
while (i - j - 1 > -1 && i + j + 1 < s.length
&& s[i - j - 1] == s[i + j + 1]) {
j++;
}
if (maxLen < j ) {
maxLen =j;
start = i - j ;
end =i + j ;
}
rad[i] = j;
maxLen = maxLen > j ? maxLen : j;
k = 1;
//当回文中包含子回文,看子回文是否超出父回文边界。 分三种情况。
while (k <= rad[i] && rad[i - k] != rad[i] - k)
{
rad[i + k] = Math.min(rad[i - k], rad[i] - k);
k++;
}
i = i + k;
j = Math.max(j - k, 0);
}
result = olds.substring(start/2,end/2);
return result;
}
}

分析
在这个问题中,回文的情况一共有两种,一种是奇数回文,一种是偶数回文,为了将他们合并成一种情况,我们可以在首尾和每两个字符中间加上一个特殊字符,如‘#’,形如”#a#b#b#c#a#”.这样我们就将所有的回文情况合并成奇数回文的情况。

在字符串s中,我们用rad[i]表示第i个字符的回文半径,可以得到s[i-rad[i],i-1] = s[i+1,i+rad[i]],只要求出了所有的rad,就求出了所有奇数长度的回文子串。

当我们得到了rad[1..i-1]的值,并通过比较对称字符得到当前字符i的rad值至少为j,求出了rad[i]。现在我们设一个指针k,从1循环到rad[i],以此来求出[i+1,i+rad[i]]的rad值。

根据定义,黑色的部分是一个回文子串,两段红色的区间全等。
因为之前已经求出了rad[i-k],所以直接用它.有3种情况:
(1)rad[i]-k < rad[i-k]
Situation1.jpg

如图,rad[i-k]的范围为墨绿色。因为黑色的部分是回文的,且墨绿色的部分超过了黑色的部分,所以rad[i+k]至少为rad[i]-k,即橙色的部分。有没有可能rad[i+k]的值大于rad[i]-k呢?这是不可能发生的,根据回文的特性我们知道,如果橙色部分以外也是回文,那么黑色的回文部分就可以向外拓展。与假设冲突。因此rad[i+k] = rad[i]-k。

(2)rad[i]-k > rad[i-k]
Situation2.jpg

如图,rad[i-k]的范围为墨绿色。因为黑色的部分是回文的,且墨绿色的部分在黑色的部分里面,根据回文特性,很容易得出:rad[i+k] = rad[i-k]。

根据上面两种情况,可以得出结论:当rad[i]-k != rad[i-k]的时候,rad[i+k] = min(rad[i]-k,rad[i-k])。

(3)rad[i]-k = rad[i-k]
Situation3.jpg
如图,通过和第一种情况对比之后会发现,因为墨绿色的部分没有超出黑色的部分,所以即使橙色的部分全等,也无法像第一种情况一样引出矛盾,因此橙色的部分是有可能全等的。但是,根据已知的信息,我们不知道橙色的部分是多长,因此就把i指针移到i+k的位置,j=rad[i-k](因为它的rad值至少为rad[i-k]),是否可以向外拓展等下个循环再做。

时间复杂度 : O(n) 。看起来程序里用到了循环嵌套,但是实际上他只对没有计量过的i进行计量。
空间复杂度 : O(n) .

如果你有更好的办法或者对我这里的描述有其他看法,请联系我。谢谢

About Me

我的博客 leonchen1024.com

我的 GitHub https://github.com/LeonChen1024

微信公众号

wechat

You forgot to set the business and currency_code for Paypal. Please set it in _config.yml.
You forgot to set the url Patreon. Please set it in _config.yml.
Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×