peace唠叨

leetcode05- Longest Palindromic Substring之Java版本

我的leetcode之旅,该篇章主要完成使用Java实现算法。这是第5篇 Longest Palindromic Substring

全部代码下载:Github链接:github链接,点击惊喜;写文章不易,欢迎大家采我的文章,以及给出有用的评论,当然大家也可以关注一下我的github;多谢;

1.题目简介:

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.我的思路:

1.最长回文字符串解法
2.一看到最长回文字符串我就想到了Manacher算法
3.算法思想:请见http://blog.sina.com.cn/s/blog_3fe961ae0101iwc2.html

3.我的AC代码

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
package com.rlovep.string;
/**
* Longest Palindromic Substring
* 我的思路:
* 1.最长回文字符串解法
* 一看到最长回文字符串我就想到了Manacher算法
* 算法思想:请见我转载的博文
* @author peace
*
*/

public class PalindromicSubstring {
public String longestPalindrome(String input) {
int pos=0;//最右回文子串的中心位置
int maxRight=0;//最右回文子串的最右端位置
int maxLength=0;//字符串最大的回文长度
int finpos=0;
int finMaxRight=0;
//添加分隔符
StringBuilder sb=new StringBuilder();
sb.append("#");
for(int i=0;i<input.length();i++){
sb.append(input.charAt(i));
sb.append("#");
}
//获得字符串数组
input=sb.toString();
char[] s= input.toCharArray();
int rl[] =new int[s.length];//存储每个位置的最大回文子串半径
for(int i=0;i<s.length;i++){
if(i<maxRight){
rl[i]=Math.min(rl[2*pos-i], maxRight-i);//核心代码
}
else{
rl[i]=1;
}
while((i-rl[i])>=0&&//不能超过左端
(i+rl[i])<s.length&&//不能超过右端
(s[i-rl[i]]==s[i+rl[i]]))
{
rl[i]+=1;
}
//更新最右回文子串的最右端位置
if((i+rl[i]-1)>maxRight){
pos=i;
maxRight=i+rl[i]-1;
}
if(rl[i]>maxLength){
finpos=i;
finMaxRight=maxRight;
maxLength=rl[i];
}
}
input=input.substring(finpos+1-maxLength,finMaxRight);
return input.replace("#", "");
}
}

好的本章介绍到这里 来自伊豚wpeace(blog.wpeace.cn)

Peace wechat
欢迎您扫一扫上面的微信公众号,订阅我的博客!
坚持原创技术分享,您的支持将鼓励我继续创作!