前往
大廳
主題

[leetcode]214. Shortest Palindrome

♙♲⚙\~O_O~/⚙♲♙ | 2021-08-13 12:00:10 | 巴幣 2 | 人氣 131

題目: 214. Shortest Palindrome
難度: Hard
目前下列解法的時間複雜度:O(n)


題目說明

給一長度 n 的字串,
問在最前面最少量補一些字元後,變成回文字串的那個回文字串。


解法

1. 寫一個O(n+m)的pattern search
2. 字串反過來
3. 在反過來的字串中找找原本的字串,記好找完反過來的字串時,原本字串的指針(註: 在下列程式碼中不是使用指標)在哪
4. 拿指針當起點,一路增加字元到反過來的字串,直到原字串尾
5. 可以回傳了

需要純嘗試寫O(n+m)的pattern search可至 https://leetcode.com/problems/implement-strstr/


source code


創作回應

相關創作

更多創作