原題連結
根據回文串的一個核心思想來解題:從中心點往兩邊擴散,來尋找回文串,這種方向相當于窮舉字元串中每一個字元為中心點。
假設回文串是奇數時,比如 “bab” ,它的中心點就隻有一個 “a”,是以從 “a” 開始向兩邊擴散
假設回文串是偶數時,比如 “baab”,它的中心點有兩個 “aa”,是以從 “aa” 開始向兩邊擴散
編寫一個輔助函數來尋找回文串,當中心點确定了之後調用輔助函數,直接傳回找到的回文串
将每次找到的回文串與之前的做對比,誰長就留誰。
class Solution {
// 主函數
public String longestPalindrome(String s) {
// 記錄最長回文串
String res = "";
// 窮舉以所有點(奇數一個點,偶數兩個點)為中心的回文串
for (int i = 0; i < s.length(); i++) {
// 假設回文串是奇數時,由一個中心點向兩邊擴散
String s1 = palindrome(s, i, i);
// 假設回文串是偶數時,由中間的兩個中心點向兩邊擴散
String s2 = palindrome(s, i, i + 1);
res = res.length() > s1.length() ? res : s1;
res = res.length() > s2.length() ? res : s2;
}
return res;
}
// 輔助函數:尋找回文串:
private String palindrome(String s, int left, int right) {
// 在區間 [0, s.length() - 1] 中尋找回文串
while (left >=0 && right < s.length()) {
// 如果是回文串時,向兩邊擴散
if (s.charAt(left) == s.charAt(right)) {
left--;
right++;
}
else{
break;
}
}
// 循環結束時的條件是 s.charAt(left) != s.charAt(right), 是以正确的區間為 [left + 1, right), 方法 substring(start, end) 區間是 [start, end), 不包含 end
return s.substring(left + 1, right);
}
}