作者ken1325 (喵奴)
看板Prob_Solve
标题[问题] LeetCode 最长回文子字串
时间Sat Dec 9 23:57:38 2017
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://webptt.com/cn.aspx?n=bbs/Prob_Solve/M.1512835062.A.7A8.html
※ 编辑: ken1325 (118.165.154.147), 12/09/2017 23:58:34
1F：推 ckc1ark: try "ab" 12/10 00:04
2F：→ ken1325: 喔喔，感谢。 12/10 00:09
3F：推 alan23273850: 如果是leetcode的话应该要用dp吧？ 12/11 11:41
这题因为最大长度是1000，所以用暴力法最後会 Time Limit Exceeded，
如果最大长度只有100，就可以用暴力法解。
其他的解法为：
1. dynamic programming，时间复杂度是O(n^2)，空间复杂度是O(n)。
2. 中心扩展法，时间复杂度是O(n^2)，空间复杂度是O(1)。
3. Manacher 演算法: 时间复杂度和空间复杂度都是O(n)。
我後来是改用中心扩展法。
4F：推 suhorng: 中心扩展法是暴力法吧 12/12 07:07
不是喔
※ 编辑: ken1325 (36.227.19.17), 12/12/2017 14:34:26
5F：推 oToToT: 他的暴力大概是直接拆下来後字串比较吧 12/13 16:44