分析Longest Palindromic Substring的JS解法

分析Longest Palindromic Substring的JS解法
1 Star2 Stars3 Stars4 Stars5 Stars 給文章打分!
Loading...

Given a string s, find the longest palindromic substring in s.
這題的意思是找出 最長連續迴文串。

思路來源於此

這裡描述了一個叫Manacher’s Algorithm的演算法。

演算法首先將輸入字串S, 轉換成一個特殊字串T,轉換的原則就是將S的開頭結尾以及每兩個相鄰的字元之間加入一個特殊的字元,例如#

例如: S = “abaaba”, T = “#a#b#a#a#b#a#”.

為了找到最長的迴文字串,例如我們當前考慮以Ti為迴文串中間的元素,如果要找到最長迴文字串,我們要從當前的Ti擴充套件使得 Ti-d … Ti d 組成最長迴文字串. 這裡 d 其實和 以Ti為中心的迴文串長度是一樣的. 進一步解釋就是說,因為我們這裡插入了 # 符號,對於一個長度為偶數的迴文串,他應該是以#做為中心的,然後向兩邊擴,對於長度是奇數的迴文串,它應該是以一個普通字元作為中心的。通過使用#,我們將無論是奇數還是偶數的迴文串,都變成了一個以Ti為中心,d為半徑兩個方向擴充套件的問題。並且d就是迴文串的長度。

程式碼在控制檯除錯如下:

首先對字串進行處理,~是規避陣列以0開頭,新增#號是為了規避字串的單複數字節。
隨後找到迴文字串最中間的位元組cs
再確定左右兩邊的位元組個數
最後用陣列方法Slice擷取回文,用正則刪除#和~

相關文章

前端開發 最新文章