【Leetcode】Longest Palindromic Substring
來源：程序員人生 發布時間：2016-06-24 17:32:38 閱讀次數：2688次
題目鏈接：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);
}
生活不易，碼農辛苦
如果您覺得本網站對您的學習有所幫助,可以手機掃描二維碼進行捐贈
