Re: [閒聊] 每日LeetCode

5. Longest Palindromic Substring 給一個字串s，回傳最長的子字串，其順序跟倒序長一樣。 Input: s = "babad" Output: "bab" 或 "aba" 老實說這一關我想超級久 能不能用排序、DP、樹什麼的去簡化計算方法 後來想半天還是想不到 決定硬尻 以每個字元為中心往左右偏移 遇到兩邊字元不同就停止 最後輸出最大的子字串 中途有遇到幾個坑 1.字串有可能是奇數跟偶數個 例如output:"aba" "bb" 一開始沒考慮到偶數個的情況 2.整個字串本身就是答案 例如input: "abcdedcba" 我一開始是一直往兩邊遇到字元相異再把index-1做成子字串去比 但是如果全部都符合他反而不會輸出結果 後來是改成先判斷index+1是不是相同 如果相同就繼續往前比 解完之後看別人的答案，靠北跟我解法一樣。原來真的就是我想太多。 TS code: function longestPalindrome (s: string): string { const getLongestSubString = (l: number, r: number): string => { let lIndex = l let rIndex = r while (lIndex >= 0 && rIndex < s.length && s[lIndex - 1] === s[rIndex + 1]) { lIndex--; rIndex++; } return s.substring(lIndex, rIndex + 1) } let result = s[0] for (let i = 0; i < s.length; i++) { const one = getLongestSubString(i, i) const two = getLongestSubString(i + 1, i) if (one.length > result.length) result = one if (two.length > result.length) result = two } return result } -- Zoosewu Yoututbe顯示PTT推文 可以在各個網站追實況或Live時使用 預覽圖: https://i.imgur.com/ZhtXdAJ.png https://i.imgur.com/WqbLNV3.png 完整介紹: https://github.com/zoosewu/PTTChatOnYoutube/tree/master/homepage 支援的網站: Youtube Twitch Holotools Nijmado Holodex --
※ 批踢踢實業坊(ptt.cc), 來自: 114.32.229.33 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1698392839.A.0F9.html

推 wwndbk: 我用這個方法會timeout欸 10/27 15:48

→ wwndbk: 用rust寫timeout c++不會 很神奇 10/27 15:48

→ wwndbk: 看解法很多人是用Manacher's algorithm 10/27 15:49

推 JIWP: 這題我記得要用馬拉車演算法 10/27 15:49