搞了一个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)