【Leetcode】Longest Palindromic Substring
发布时间：2020-12-13 21:09:03 所属栏目：PHP教程 来源：网络整理
导读：题目链接：https://leetcode.com/problems/longest-palindromic-substring/ 题目： Given a string S ,find the longest palindromic substring in . You may assume that the maximum length of is 1000,and there exists one unique longest palindromic s
|
题目链接：https://leetcode.com/problems/longest-palindromic-substring/ Given a string S,find the longest palindromic substring in . You may assume that the maximum length of 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);
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);
}
（编辑：李大同） 【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容! |