Re: [閒聊] 每日leetcode
214. Shortest Palindrome
## 思路
找從頭開始最長的回文 再把後段reverse補到前面
ex. abac -> 開頭最長回文3 (aba), 前面補c -> cabac
abcdc -> 開頭最長回文1 (a), 前面補cdcb -> cdcbabcdc
用KMP建表, 再從後面掃回來 最後j就是最長回文的長度
--
原本是用Manacher找回文結果TLE = =
## Code
```python
class Solution:
def shortestPalindrome(self, s: str) -> str:
n = len(s)
lps = [0] * n
j = 0
for i in range(1, n):
while j and s[i] != s[j]:
j = lps[j-1]
if s[i] == s[j]:
j += 1
lps[i] = j
j = 0
for i in range(n):
while j and s[~i] != s[j]:
j = lps[j-1]
if s[~i] == s[j]:
j += 1
return s[j:][::-1] + s
```
--
https://i.imgur.com/kyBhy6o.jpeg
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 185.213.82.171 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1726803306.A.DB6.html
推
09/20 17:30,
1年前
, 1F
09/20 17:30, 1F
討論串 (同標題文章)
完整討論串 (本文為第 884 之 1548 篇)：