LeetCode【五】. Longest Palindromic Substring -java实现
LeetCode【5】. Longest Palindromic Substring --java实现
Longest Palindromic Substring
一、题目如下：
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.
题目要求给定字符串的最大对称子字符串，如“aaabccbacc”的最大对称子字符串为“abccba”。
二、思路：
以每个字符或两个字符的中间作为中心向两边比较过去，并判断是否为对称子字符。思路很简单，两种情况示意图如下：
图一、两种对称情况示意图
如图，对于对称字符串，可能出现如上两种情况。一种为A“偶对称”，以中隔线互相对称；另一种为B“奇对称”，以中间一字符为中心对称。通过i从0一直扫向字符串的尾部，每次前进0.5，并以i为中心，向两端扫去进行判断。时间复杂度为O(n^2)，最坏情况为整个字符串所有字符相同，那么每次扫都得扫到尽头。
三、Java程序
</pre><pre name="code" class="java">public class Solution {
public String longestPalindrome(String s) {
int down = 0,up = 0,count = 0; //分别记录扫字符串时的上下区间及字符串长度
int sl = s.length();
int maxl = 0;
int subDown = 0, subUp = 0; //目标子字符串的上下区间
String subS = new String("");
if(sl==0)
return "";
//1. 找出目标子字符串的中间位置及上下限
for(double i=0; i<=sl-1; i=i+0.5)
{
down = (int)Math.floor(i);
up = (int)Math.ceil(i);
if((i%1==0.5)&&sl!=0) //判断i所属情况（A或B）
{
count = 0;
}else
{
count = 1;
down--;
up++;
}
//2. 以i为中心向两边扫描
while(!(down<0||up>sl-1))
{
if(s.charAt(down)!=(s.charAt(up)))
{
break; //2.1. 当以i为中心对称的俩字符不相等则跳出扫描
}else{ //2.2. 当以i为中心对称的俩字符相等则继续分别向两边移动
count+=2;
down--;
up++;
}
}
//3. 更新最长字符串
if(count>maxl)
{
maxl = count;
subDown = down;
subUp = up;
}
}
//3.1 由于在扫描时，先移动后再判断，停止时其实前后都多移动了一个单位，这里进行一个单位的恢复
subDown++;
subUp--;
subS = s.substring(subDown,subUp+1);
return subS;//返回对称子字符串
}
}
扩展学习：该文章介绍了几种方法Java Longest Palindromic Substring(最长回文字符串)