→ sustainer123: 大師 09/23 20:49
推 oin1104: 今天每日找字串的時候可以用kmp 會快一點點 09/23 20:54
→ oin1104: 如果側資大一點的話大概就逼你用kmp了很麻煩就是了 09/23 20:54
推 sustainer123: dp結合kmp 逼人上吊是吧 09/23 20:54
搞了一個dp的樣子
但速度不是很好
應該有哪裡可以改善
板友 幫幫肥肥
def minExtraChar(self, s: str, dictionary: List[str]) -> int:
dct = set(word for word in dictionary)
@lru_cache()
def dp(r) -> int:
if r<0:
return 0
ans = r+1
for l in range(r,-1,-1):
if s[l:r+1] in dct:
ans = min(ans, dp(l-1))
else:
ans = min(ans, r-l+1+dp(l-1))
return ans
return dp(len(s)-1)
--
https://i.imgur.com/QaQrl0t.jpeg
https://i.imgur.com/yXpuYNA.jpeg
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 125.229.37.69 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1727095772.A.06F.html