JavaScript求解最長回文子串的方法分享
題目描述
給定一個字符串 s,找到 s 中最長的回文子串。你可以假設 s 的最大長度為 1000。
示例 1:
輸入: "babad" 輸出: "bab" 註意: "aba" 也是一個有效答案。
示例 2:
輸入: "cbbd" 輸出: "bb"
題解
回文:指一個正讀和反讀都相同的字符串,例如,“aba” 是回文,而 “abc” 不是。
解決方案
思路一:暴力法
即通過雙重遍歷來獲取目標字符串所有的子串,push 到一個數組裡面,然後根據字符串長度排序,從最長字串開始循環校驗,第一個為回文的子串就是我們要的結果
復雜度分析
- 時間復雜度:O(n^3)
- 空間復雜度:O(1)
/** * @param {string} s * @return {string} */ var longestPalindrome = function(s) { let m = [] let res = '' for(let i=0; i<s.length; i++) { for(let j = i; j < s.length; j++) { m.push(s.slice(i, j+1)) } } m.sort(function(a,b){ return b.length - a.length }) for (let i of m) { if (i === i.split('').reverse().join('')) { res = i break; } } return res }
上面代碼在目標字符串長度過大的時候,會超出時間限制,遠遠超出O(n^2) 的理想時間復雜度,這是因為過多的for 循環,js 自帶函數使用過多造成的,優化一下
var longestPalindrome = function(s) { let m = [] let res = '' for(let i=0; i<s.length; i++) { for(let j = i; j < s.length; j++) { if (s[i] != s[j]) break let ele = s.slice(i, j+1) if (ele === ele.split('').reverse().join('') && ele.length > res.length) { res = ele } } } return res }
看起來好多瞭,但是依然通不過Leecode 的測試,我覺得必須要把 slice split reverse join 這些函數都幹掉才行,也可能 JS 語言效率確實慢一些
思路二:最長公共字串
反轉 S,使之變成 S'。找到 S 和 S' 之間最長的公共子串,判斷是否是回文
復雜度分析
- 時間復雜度:O(n^2)
- 空間復雜度:O(n^2)
/** * @param {string} s * @return {string} */ var longestPalindrome = function(s) { let rs = s.split('').reverse().join('') let size = s.length let len = 0 let end = 0 let a = new Array(size) for (let i = 0; i < size; i++) { a[i] = new Array() } for (let i = 0; i < size; i++) { for(let j = 0; j < size; j++) { if (s[i] === rs[j]) { if (i > 0 && j > 0) { a[i][j] = a[i-1][j-1] + 1 } else { a[i][j] = 1 } if(a[i][j] > len) { let beforeIndex = size - 1 - j if (beforeIndex + a[i][j] -1 == i) { len = a[i][j] end = i } } } else { a[i][j] = 0 } } } return s.slice(end-len+1, end+1) }
思路三:中心拓展
遍歷一遍字符串,以每個字符為中心向兩邊判斷,是否為回文字符串
復雜度分析
- 時間復雜度:O(n^2)
- 空間復雜度:O(1)
/** * @param {string} s * @return {string} */ var longestPalindrome = function(s) { let size = s.length let start = 0 let len = 0 //字串長度 // 奇數長度的回文字串 for (let i = 0; i < size; i++) { let left = i - 1 let right = i + 1 while (left >= 0 && right < size && s[left] == s[right]) { left -- right ++ } if (right - left - 1 > len) { start = left +1 len = right -left -1 } } // 偶數長度的回文字串 for (let i = 0; i < size; i++) { let left = i let right = i + 1 while (left >= 0 && right < size && s[left] == s[right]) { left-- right++ } if (right -left -1 > len) { start = left + 1 len = right -left -1 } } return s.slice(start, start + len) }
思路四:Manacher 算法
manacher 算法涉及中心拓展法、動態規劃,是manacher 1975年發明出來用來解決最長回文子串的線性算法
// 第一步 var longestPalindrome = function(s) { let size = s.length if (size < 2) { return s } let str = addBoundaries(s, '#') let formatSize = 2 * size +1 let maxSize = 1 let start = 0 for (let i=0; i<formatSize; i++) { let curSize = centerSpread(str, i) if (curSize > maxSize) { maxSize = curSize start = (i - maxSize)/2 } } return s.slice(start, start + maxSize) } // 處理原字符串 var addBoundaries = function(s, divide) { let size = s.length if (size === 0) { return '' } if (s.indexOf(divide) != -1) { throw new Error('參數錯誤,您傳遞的分割字符,在輸入字符串中存在!') } return divide + s.split('').join(divide) + divide } // 輔助數組 var centerSpread = function(s, center) { // left = right 的時候,此時回文中心是一個空隙,回文串的長度是奇數 // right = left + 1 的時候,此時回文中心是任意一個字符,回文串的長度是偶數 let len = s.length let i = center - 1 let j = center + 1 let step = 0 while (i >= 0 && j < len && s.charAt(i) == s.charAt(j)) { i-- j++ step++ } return step } longestPalindrome('ababadfglldf;hk;lhk')
manacher 算法的工作,就是對上面代碼中的輔助數組 p 進行優化,使時間復雜度的降到O(n^2)
// 完整 var longestPalindrome = function(s) { let size = s.length if (size < 2) { return s } let str = addBoundaries(s, '#') let formatSize = 2 * size +1 let p = new Array(formatSize).fill(0) let maxRight = 0 let center = 0 let maxSize = 1 let start = 0 for (let i=0; i<formatSize; i++) { if (i < maxRight) { let mirror = 2 * center - i; // Manacher 算法的核心 p[i] = Math.min(maxRight - i, p[mirror]); } // 下一次嘗試擴散的左右起點,能擴散的步數直接加到 p[i] 中 let left = i - (1 + p[i]); let right = i + (1 + p[i]); // left >= 0 && right < formatSize 保證不越界 // str.charAt(left) == str.charAt(right) 表示可以擴散 1 次 while (left >= 0 && right < formatSize && str.charAt(left) == str.charAt(right)) { p[i]++; left--; right++; } // 根據 maxRight 的定義,它是遍歷過的 i 的 i + p[i] 的最大者 // 如果 maxRight 的值越大,進入上面 i < maxRight 的判斷的可能性就越大,這樣就可以重復利用之前判斷過的回文信息瞭 if (i + p[i] > maxRight) { // maxRight 和 center 需要同時更新 maxRight = i + p[i]; center = i; } if (p[i] > maxSize) { // 記錄最長回文子串的長度和相應它在原始字符串中的起點 maxSize = p[i]; start = (i - maxSize) / 2; } } return s.slice(start, start + maxSize) } var addBoundaries = function(s, divide) { let size = s.length if (size === 0) { return '' } if (s.indexOf(divide) != -1) { throw new Error('參數錯誤,您傳遞的分割字符,在輸入字符串中存在!') } return divide + s.split('').join(divide) + divide } longestPalindrome('babb')
到此這篇關於JavaScript求解最長回文子串的方法分享的文章就介紹到這瞭,更多相關JavaScript最長回文子串內容請搜索WalkonNet以前的文章或繼續瀏覽下面的相關文章希望大傢以後多多支持WalkonNet!
推薦閱讀:
- 利用JavaScript為句子加標題的3種方法示例
- JS字符串分割方法整理匯總示例講解(3種截取方法和6個輔助方法)
- JS超出精度數字問題的解決方法
- js算法實例之字母大小寫轉換
- JS常用的4種截取字符串方法