每日一算--最長迴文子串
摘要：
給定一個字串 s，找到 s 中最長的迴文子串。你可以假設 s 的最大長度為 1000。
示例1
輸入: "babad"
輸出: "bab"
注意: "aba" 也是一個有效答案。
複製程式碼
示例2
輸入: "cbbd&#...
給定一個字串 s，找到 s 中最長的迴文子串。你可以假設 s 的最大長度為 1000。
示例1
輸入: "babad" 輸出: "bab" 注意: "aba" 也是一個有效答案。 複製程式碼
示例2
輸入: "cbbd" 輸出: "bb" 複製程式碼
示例3
輸入: "cbad" 輸出: "" 複製程式碼
日常找規律
一句話解釋迴文的意思是正著念和倒著念一樣，如：上海自來水來自海上，山西運煤車煤運西山等，瞬間感覺自己在聽郭德綱相聲
- 暴力法將選出所有子字串可能的開始和結束位置，並檢驗它是不是迴文。
- 改進暴力法，我們首先觀察如何避免在驗證迴文時進行不必要的重複計算。考慮 “ababa” 這個示例。如果我們已經知道“bab”是迴文，那麼很明顯，“ababa” 一定是迴文，因為它的左首字母和右尾字母是相同的得出動態方程
- P(i,i)=trueP(i,i+1)=(Si == Si+ 1)
實現方式
暴力搜尋
時間複雜度 O(N^3)
const longestPalindrome = function(s) {
if (!s) return ''
let longest = s[0]
let str, i, j, len
const isPalindrom = function (left, right) {
while (left < right && s[left] === s[right]) {
left++;
right--;
}
return left >= right;
}
for (len = 2; len <= s.length; len++) {
for (i = 0; i < s.length; i++) {
j = i + len - 1;
if (isPalindrom(i, j)) {
str = s.slice(i, j + 1);
if (longest.length < str.length) longest = str;
}
}
}
return longest
}
複製程式碼
動態規劃
時間複雜度 O(N^3) 空間複雜度 O(N^2)
迴文字串定位為: dp(start,end)
- start是迴文字串的起始位置
- end 是迴文字串的截止位置
- 迴文字串要滿足的基本條件為： str[start] == str[end] 並且dp(start+1,end-1) 也為迴文字串
-
邊界條件為：
start-end=0, 例如:"a"
start-end=1 && str[start] == str[end],例如："aa","bb"
const longestPalindrome = function(s) {
let i, j, len
const isPalindrom = new Array(s.length);
for (i = 0; i < s.length; i++) {
isPalindrom[i] = new Array(s.length).fill(false);
}
let maxLen = 1, longestBegin = 0;
for (i = 0; i < s.length; i++) {
isPalindrom[i][i] = true;
if (i < s.length - 1 && s[i] === s[i + 1]) {
isPalindrom[i][i + 1] = true;
maxLen = 2;
longestBegin = i;
}
}
for (len = 3; len <= s.length; len++) {
for (i = 0; i < s.length; i++) {
j = len + i - 1;
if (s[i] === s[j] && isPalindrom[i + 1][j - 1]) {
isPalindrom[i][j] = true;
maxLen = len;
longestBegin = i;
}
}
}
return s.slice(longestBegin, longestBegin + maxLen);
}
複製程式碼
優化降低空間複雜度
空間複雜度降到 O(1)，只存找到的最長迴文串即可。列舉軸心位置，並進行擴充套件。如果是迴文，則軸心兩邊的字元應該對稱相等。需要考慮到長度奇偶情況的不同，如果是奇數長度，軸心就是一個字元；如果是偶數長度，軸心則不在字串中
const longestPalindrome = function(s) {
if (!s) return '';
let longest = s[0];
let expandAroundCenter = function (left, right) {
while (left >= 0 && right < s.length && s[left] === s[right]) {
left--;
right++;
}
return s.slice(left + 1, right);
}
for (let i = 0; i < s.length; i++) {
let odd = expandAroundCenter(i, i);
if (odd.length > longest.length) longest = odd;
let even = expandAroundCenter(i, i + 1);
if (longest.length < even.length) longest = even;
}
return longest;
}
複製程式碼
優化降低時間複雜度
相比降低空間複雜度，降低時間複雜度要難得多。這裡有一個 O(N) 時間複雜度的演算法，叫做 Manacher 演算法
const longestPalindrome = function(s) {
s = '^#' + s.split('').join('#') + '#$';
let radius = new Array(s.length).fill(0);
let C = 0, centerIndex = 0, maxRight = 0, maxLen = 0;
for (let i = 1; i < s.length - 1; i++) {
# 計算初始迴文半徑, i' = 2 * C - i
radius[i] = (maxRight > i) ? Math.min(maxRight - i, radius[2 * C - i]) : 0;
# 擴充套件半徑
while (s[i + 1 + radius[i]] && s[i - 1 - radius[i]] && s[i + 1 + radius[i]] === s[i - 1 - radius[i]]) radius[i]++;
# 更新當前搜尋的最大右邊界和位置
if (i + radius[i] > maxRight) {
C = i;
maxRight = i + radius[i];
}
# 更新最大回文串長度及位置
if (maxLen < radius[i]) {
maxLen = radius[i];
centerIndex = i;
}
}
return s.slice((centerIndex - maxLen), (centerIndex + maxLen + 1)).split('#').join('');
}
複製程式碼