【Leetcode】Longest Palindromic Substring
来源：程序员人生 发布时间：2016-06-24 17:32:38 阅读次数：2476次
题目链接：https://leetcode.com/problems/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.
思路：
遍历该字符串每个位置，并判断以该位置为中位点的最长回文串的长度，复杂度为O(n^2)。 要注意如果回文串是奇数长度和偶数长度不同。所以需要遍历判断两次。1次默许该点为中心的回文串是奇数长，1次默许是偶数长。
算法：
public String longestPalindrome(String s) {
if (s.length() <= 1) {
return s;
}
if (s.length() == 2) {
if (s.charAt(0) == s.charAt(1)) {
return s;
} else {
return s.charAt(0) + "";
}
}
String res = "";
int maxLen = 0;
// 对奇位点判断
for (int i = 1; i < s.length() - 1; i++) {
String str = calPalin(s, i - 1, i + 1);
if (maxLen < str.length()) {
maxLen = str.length();
res = str;
}
}
// 对偶位点判断
for (int i = 1; i < s.length(); i++) {
String str = calPalin(s, i - 1, i);
if (maxLen < str.length()) {
maxLen = str.length();
res = str;
}
}
return res;
}
public String calPalin(String s, int left, int right) {
if (left < 0 && right >= s.length()) {
return "";
}
while (left >= 0 && right < s.length() && s.charAt(left) == s.charAt(right)) {
left--;
right++;
}
return s.substring(left + 1, right);
}
生活不易，码农辛苦
如果您觉得本网站对您的学习有所帮助,可以手机扫描二维码进行捐赠
