溫馨提示×
您好，登錄后才能下訂單哦！
點擊 登錄注冊 即表示同意《億速云用戶服務條款》
您好，登錄后才能下訂單哦！
本篇內容主要講解“JavaScript最長回文子串怎么求”，感興趣的朋友不妨來看看。本文介紹的方法操作簡單快捷，實用性強。下面就讓小編來帶大家學習“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 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最長回文子串怎么求”有了更深的了解，不妨來實際操作一番吧！這里是億速云網站，更多相關內容可以進入相關頻道進行查詢，關注我們，繼續學習！
免責聲明：本站發布的內容（圖片、視頻和文字）以原創、轉載和分享為主，文章觀點不代表本網站立場，如果涉及侵權請聯系站長郵箱：is@yisu.com進行舉報，并提供相關證據，一經查實，將立刻刪除涉嫌侵權內容。
