直接的实现方法:

取字符串的所有子串,逐一确定子串是否为回文串,并比较其长度。这里给出确定一个字符串是否为回文串:

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

取字符串的所有子串需要多次循环语句实现,时间复杂度较高

另一种实现方法:

根据上述判断一个字符串是否为回文串的思路分析,在遍历字符串的过程中,如果某一处满足回文串的初始条件,则以其为回文串中心,接着比较其两侧的元素是否满足回文串条件,从而确定最长回文子串。

单个元素即为回文串,所以不考虑元素为奇数个回文串的初始条件。对于元素为偶数个的回文串,则一定要满足中心相邻的两个元素相同。

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
public String Longest(String s){
int length = s.length();
if (length == 0)
return null;
String longest = s.substring(0, 1);//初始化
for(int i = 1; i < length; i++){
String odd = Palindrome(i, i, s);//回文子串的元素为奇数个
if(odd.length() > longest.length())
longest = odd;
if(s.charAt(i - 1) == s.charAt(i)){//相邻两个元素相同,是回文子串的元素为偶数个的前提
String even = Palindrome(i - 1, i, s);
if(even.length() > longest.length())
longest = even;
}
}
return longest;
}
public String Palindrome(int start, int end, String s){
while(start - 1 >= 0 && end + 1 < s.length() && s.charAt(start - 1) == s.charAt(end + 1)){
//回文串的满足条件
start--;
end++;
}
return s.substring(start, end + 1);
}

在遍历字符串、取子串时,都要注意其下标的范围

参考资料:

Leetcode Solution of Longest Palindromic Substring in Java