前往
大廳
主題

[leetcode]1392. Longest Happy Prefix

♙♲⚙\~O_O~/⚙♲♙ | 2021-08-17 12:00:01 | 巴幣 2 | 人氣 244

題目: 1392. Longest Happy Prefix
難度: Hard
目前下列解法的時間複雜度: O(n)


題目說明

給一字串 s (長度n) ,
問除了自己本身以外,最長的前綴等於後綴的字串為何。


解法: KMP

1. 建完 KMP 的倒帶指針(註: 該指針在程式碼中不是使用指標)後,等同拿到每個位置從往前多遠開始,會等於前綴
2. 拿最後一格的指針看一下多遠多長,然後回傳 const char* 指標,剩下交給 string 的 constructor 幫你完成


source code


創作回應

相關創作

更多創作