題目要求
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.
??題目翻譯：給定一個字符串拭荤，找到最長的回文字串截碴，假定字符串長度最大為1000，并存在唯一的最大回文子串瞬沦。
題目分析一
假設(shè)s(j+1,k-1)是一個回文串添坊，且s[j]==s[k]区匠，可證，s(j,k)也一定是一個回文串帅腌。由此啟發(fā)，我們可以記錄之前的結(jié)果作為啟發(fā)信息麻汰，以利于后面的判斷和搜索速客。該算法的復(fù)雜度為O(n^2)。
package com.linsiyue;
public class Solution {
public String longestPalindrome(String s) {
int n = s.length();
int lo = 0,maxLen = 0;
// 聲明一個boolean型二維數(shù)值五鲫，s(j,k)為回文串則boolean[i][j]=true
// 其中 i<=j
boolean[][] dp = new boolean[n][n];
for (int i = n-1; i >= 0; i--) {
for (int j = i; j < n; j++) {
// 關(guān)鍵點是j-i<3這個邊界條件的加入溺职，搜索問題要定義明確邊界條件
// 當(dāng)字符串長度為1或i=0時，dp[i+1][j-1]會出現(xiàn)數(shù)組越界的錯誤
// 當(dāng)s.charAt(i)==s.charAt(j) && j-i<3 時位喂，是回文串浪耘，如aba,aa
dp[i][j] = s.charAt(i)==s.charAt(j) && (j-i<3 ||dp[i+1][j-1]);
if (dp[i][j] && j-i+1>maxLen){
lo = i;
maxLen = j-i+1;
}
}
}
return s.substring(lo,lo+maxLen);
}
}
題目分析二
長度為偶數(shù)的回文串，有如下性質(zhì)：中間的兩個字符s[i]==s[i+1],且s[i-1]==s[i+2]塑崖，依次向兩邊對稱遞推七冲，直到碰到回文串邊界。長度為奇數(shù)的回文串规婆，最中間的數(shù)的兩邊的數(shù)相等澜躺，即s[i-1]==s[i+1]，隱含著一個重要條件抒蚜，s[i]==s[i]掘鄙，有了該隱含條件，遞推模式即如偶數(shù)嗡髓。
??因此奇偶數(shù)情況可以抽象為一個模型：由中間向兩邊操漠，依次比較軸對稱的兩個字符，直到兩個字符不相等饿这，即可獲得該回文串的起始地址及長度浊伙。
??函數(shù)extendPalindrome(String s, int j, int k)即是該模型的實現(xiàn)。
package com.linsiyue;
public class Solution {
private int lo, maxLen;
public String longestPalindrome(String s) {
int len = s.length();
if (len<2)
return s;
for (int i = 0; i < len-1; i++) {
// 奇數(shù)情況
extendPalindrome(s,i,i);
// 偶數(shù)情況
extendPalindrome(s,i,i+1);
}
return s.substring(lo, lo+maxLen);
}
public void extendPalindrome(String s, int j, int k) {
while (j>=0 && k<s.length() && s.charAt(j)==s.charAt(k)){
j--;
k++;
}
// 跳出while循環(huán)時蛹稍，回文串的開頭和結(jié)尾游標(biāo)分別被-1和+1
// 因此計算長度的補(bǔ)回：len=(k-1)-(j+1)+1=k-j-1
if(maxLen < k-j-1){
lo = j+1;
maxLen = k-j-1;
}
}
}
