[問題] LeetCode 最長回文子字串

看板Prob_Solve作者 (喵奴)時間6年前 (2017/12/09 23:57), 6年前編輯推噓4(4推 0噓 1→)
留言5則, 5人參與, 6年前最新討論串1/1
LeetCode 5. Longest Palindromic Substring https://leetcode.com/problems/longest-palindromic-substring/description/ Given a string s, find the longest palindromic substring in s. You may assume that the maximum length of s is 1000. 這題要在一個字串裡面找出最長的子字串 https://paste.ofcode.org/WpkzvXdgCx2zXJGhULWYtm 這是我用暴力法寫的，但是submit後他說有 Wrong Answer 我不知道錯在哪裡 有人能幫我看看嗎？ 感謝 -- ※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 118.165.154.147 ※ 文章網址: https://www.ptt.cc/bbs/Prob_Solve/M.1512835062.A.7A8.html ※ 編輯: ken1325 (118.165.154.147), 12/09/2017 23:58:34
推
12/10 00:04, 6年前 , 1F
try "ab"
12/10 00:04, 1F
→
12/10 00:09, 6年前 , 2F
喔喔，感謝。
12/10 00:09, 2F
推
12/11 11:41, 6年前 , 3F
如果是leetcode的話應該要用dp吧？
12/11 11:41, 3F
這題因為最大長度是1000，所以用暴力法最後會 Time Limit Exceeded， 如果最大長度只有100，就可以用暴力法解。 其他的解法為： 1. dynamic programming，時間複雜度是O(n^2)，空間複雜度是O(n)。 2. 中心擴展法，時間複雜度是O(n^2)，空間複雜度是O(1)。 3. Manacher 演算法: 時間複雜度和空間複雜度都是O(n)。 我後來是改用中心擴展法。
推
12/12 07:07, 6年前 , 4F
中心擴展法是暴力法吧
12/12 07:07, 4F
不是喔 ※ 編輯: ken1325 (36.227.19.17), 12/12/2017 14:34:26
推
12/13 16:44, 6年前 , 5F
他的暴力大概是直接拆下來後字串比較吧
12/13 16:44, 5F
‣ 更多 ken1325 的文章
文章代碼(AID): #1QB0VsUe (Prob_Solve)