Re: [閒聊] 每日leetcode
看板Marginalman作者DJYOSHITAKA (franchouchouISBEST)時間1年前 (2024/09/23 20:49)推噓2(2推 0噓 2→)留言4則, 2人參與討論串895/1554 (看更多)
搞了一個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
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 125.229.37.69 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1727095772.A.06F.html
→
09/23 20:49,
1年前
, 1F
09/23 20:49, 1F
推
09/23 20:54,
1年前
, 2F
09/23 20:54, 2F
→
09/23 20:54,
1年前
, 3F
09/23 20:54, 3F
推
09/23 20:54,
1年前
, 4F
09/23 20:54, 4F
討論串 (同標題文章)
完整討論串 (本文為第 895 之 1554 篇)：