題目：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.
Example:
Input: "babad"
Output: "bab"
Note: "aba" is also a valid answer.
Example:
Input: "cbbd"
Output: "bb"
算法分析
解法一：
暴力解法，時(shí)間復(fù)雜度：O(n^n)。
遍歷每一個(gè)字符，然后左右依次向兩邊比較是否相等，繼而判斷是否滿足回文串的條件，找出最長(zhǎng)即可。注意需要判斷回文長(zhǎng)度為奇，偶長(zhǎng)度的情況。
解法二：
- 動(dòng)態(tài)規(guī)劃，時(shí)間復(fù)雜度:O(n^2)。
dp[i][j] 表示從i~j的子串是否是回文串。
動(dòng)態(tài)轉(zhuǎn)移方程：
dp[i][j] = {
dp[i-1][j + 1] : s[i] == s[j],
false : s[i] != s[j]
}
Swift實(shí)現(xiàn)
class Solution {
func longestPalindrome(_ s: String) -> String {
var dp:[[Bool]] = [];
if s.count <= 1{
return s;
}
var longest:Int = 1;
var left:Int = 0;
var right:Int = 0;
for var i in 0...s.count - 1{
var eachRow:[Bool] = [];
for var j in 0...s.count - 1{
if i == j{
eachRow.append(true);
}else{
eachRow.append(false);
}
}
dp.append(eachRow);
}
var i:Int = 0;
var j:Int = 0;
for var character_j in s {
if j == 0 {
j += 1;
continue;
}
i = 0;
for var character_i in s {
if character_i == character_j {
dp[i][j] = dp[i + 1][j - 1] || j - i <= 1;
if dp[i][j] && j - i + 1 > longest{
longest = j - i + 1;
left = i;
right = j;
}
}else{
dp[i][j] = false;
}
i += 1;
if i >= j{
break;
}
}
j += 1;
}
let leftIndex = s.index(s.startIndex, offsetBy: left);
let rightIndex = s.index(s.startIndex, offsetBy: right);
return String(s[leftIndex...rightIndex]);
}
}
AC結(jié)果：可能是swift處理字符串的效率問題會(huì)超時(shí)。
Time Limit Exceeded
第三種解法
- Manacher算法,時(shí)間復(fù)雜度：O(n)。
Manacher's ALGORITHM: O(n)時(shí)間求字符串的最長(zhǎng)回文子串思路分析這里介紹的很清晰，
此處只是簡(jiǎn)單介紹與Swift實(shí)現(xiàn)。
首先解決回文長(zhǎng)度為奇偶的問題
- 插樁處理，整個(gè)字符串的前后間隔處插入'#'字符，最終得到的字符串就一定是奇數(shù)長(zhǎng)度，回文的長(zhǎng)度也一定是奇數(shù)長(zhǎng)度。
我們來舉一個(gè)例子："cbbd"。先進(jìn)行插樁處理 -> "#c#b#b#d#"。我們定義一個(gè)數(shù)組P[i]用來記錄以i處的字符作為軸心的最大的回文半徑。我們自己計(jì)算得到如下的對(duì)應(yīng)關(guān)系：
# c # b # b # d #
1 2 1 2 3 2 1 2 1
解決計(jì)算P[i]問題
我們?cè)黾觾蓚€(gè)輔助量id,max分別代表當(dāng)前計(jì)算的到最右邊回文覆蓋的軸心與最右下標(biāo)。借用Manacher's ALGORITHM: O(n)時(shí)間求字符串的最長(zhǎng)回文子串中的兩張圖解：
當(dāng) mx - i > P[j] 的時(shí)候，以S[j]為中心的回文子串包含在以S[id]為中心的回文子串中，由于 i 和 j 對(duì)稱，以S[i]為中心的回文子串必然包含在以S[id]為中心的回文子串中，所以必有 P[i] = P[j]，見下圖。
當(dāng) P[j] >= mx - i 的時(shí)候，以S[j]為中心的回文子串不一定完全包含于以S[id]為中心的回文子串中，但是基于對(duì)稱性可知，下圖中兩個(gè)綠框所包圍的部分是相同的，也就是說以S[i]為中心的回文子串，其向右至少會(huì)擴(kuò)張到mx的位置，也就是說 P[i] >= mx - i。至于mx之后的部分是否對(duì)稱，就只能老老實(shí)實(shí)去匹配了。
得到的計(jì)算的方程式：
//記j = 2 * id - i，也就是說 j 是 i 關(guān)于 id 的對(duì)稱點(diǎn)(j = id - (i - id))
P[i] = {
P[j] ,mx - i > P[j]
mx - i, mx - i <= P[j]
}
Swift 實(shí)現(xiàn)
class Solution {
func longestPalindrome(_ s: String) -> String {
if s.count <= 1 {
return s;
}
// 1.間隔之間先插入#
var newString:String = "#";
for var character in s {
newString.append(character);
newString = newString + "#";
}
let characters = Array(newString);
// 2.遍歷找出以每個(gè)節(jié)點(diǎn)作為軸最長(zhǎng)半徑
var maxId:Int = 0;
var max:Int = 0;
var ids:[Int] = [];
ids.append(1);
var maxLength:Int = 1;
var maxLengthIndex = 0;
for var i in 1...characters.count - 1 {
var j:Int = maxId - (i - maxId);
if max > i && j >= 0 {
ids.append(min(ids[j], max - i));
}else{
ids.append(1);
}
while i + ids[i] <= characters.count - 1 && i - ids[i] >= 0 && characters[i + ids[i]] == characters[i - ids[i]]{
ids[i] += 1;
}
if i + ids[i] - 1 > max {
maxId = i;
max = i + ids[i] - 1;
}
if ids[i] > maxLength{
maxLength = ids[i];
maxLengthIndex = i;
}
}
let leftIndex = s.index(s.startIndex, offsetBy: (maxLengthIndex - (maxLength - 1))/2);
let rightIndex = s.index(leftIndex, offsetBy:maxLength - 1 - 1);
return String(s[leftIndex...rightIndex]);
}
}
AC結(jié)果：
Accepted
