T5. Longest Palindromic Substring 【Medium】
題目
給出一個(gè) string 串 s篓跛，找到里面最長(zhǎng)的回文串颖杏。你可以假設(shè) s 最長(zhǎng)的長(zhǎng)度是 1000奶赠。
回文串：一個(gè)正讀和反讀都一樣的字符串
示例1：
輸入: "babad"
輸出: "bab"
提示: "aba" 也是一個(gè)正確的解答.
示例2：
輸入: "cbbd"
輸出: "bb"
思路
主要思路：
回文串分成奇數(shù)和偶數(shù)兩種捎迫，通過(guò)從中心向外擴(kuò)散來(lái)找對(duì)應(yīng)的串武鲁。然后循環(huán)從左到右更換中心點(diǎn)灭翔。
示例：
'|'對(duì)應(yīng)的是指向的標(biāo)號(hào)
奇數(shù)串 babaacd babaacd babaacd 得到串a(chǎn)ba
| | | | |
偶數(shù)串 babaacd babaacd 得到串a(chǎn)a
|| | |
具體可以看下面的代碼以及注釋
代碼
代碼取自 Top Solution嵌言，稍作注釋
public class Solution {
//lo表示回文字符串首字符序號(hào)嗅回，macLen表示回文子串的長(zhǎng)度
private int lo, maxLen;
public String longestPalindrome(String s) {
//得到字符串長(zhǎng)度
int len = s.length();
//若長(zhǎng)度小于2，則就是回文摧茴，直接返回
if (len < 2)
return s;
//用for循環(huán)一個(gè)個(gè)試過(guò)去
for (int i = 0; i < len-1; i++) {
//當(dāng)回文串是奇數(shù)的時(shí)候
extendPalindrome(s, i, i);
//當(dāng)回文串是偶數(shù)的時(shí)候
extendPalindrome(s, i, i+1);
}
//返回最長(zhǎng)回文串
return s.substring(lo, lo + maxLen);
}
//從中間往外擴(kuò)散然后得到回文串
private void extendPalindrome(String s, int j, int k) {
while (j >= 0 && k < s.length() && s.charAt(j) == s.charAt(k)) {
//通過(guò)j--,k++向外擴(kuò)散
j--;
k++;
}
//當(dāng)找到比較長(zhǎng)的串時(shí)保存串初始符號(hào)位置以及長(zhǎng)度
if (maxLen < k - j - 1) {
lo = j + 1;
maxLen = k - j - 1;
}
}}
