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

[ken1325 (喵奴)]

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
推 ckc1ark: try "ab"
→ ken1325: 喔喔，感謝。
推 alan23273850: 如果是leetcode的話應該要用dp吧？
這題因為最大長度是1000，所以用暴力法最後會 Time Limit Exceeded，

如果最大長度只有100，就可以用暴力法解。

其他的解法為：

1. dynamic programming，時間複雜度是O(n^2)，空間複雜度是O(n)。

2. 中心擴展法，時間複雜度是O(n^2)，空間複雜度是O(1)。

3. Manacher 演算法: 時間複雜度和空間複雜度都是O(n)。

我後來是改用中心擴展法。

推 suhorng: 中心擴展法是暴力法吧
不是喔
※ 編輯: ken1325 (36.227.19.17), 12/12/2017 14:34:26
推 oToToT: 他的暴力大概是直接拆下來後字串比較吧