leetcode-139-单词拆分

题目描述：

方法一：动态规划 O(n^2) O(n)

class Solution: def wordBreak(self, s: str, wordDict: List[str]) -> bool: maxlen=0 for word in wordDict: if len(word)>maxlen: maxlen=len(word) res=[0]*len(s) for i in range(len(s)): p=i while(p>=0 and i-p<=maxlen): # 两个条件 if (res[p]==1 and s[p+1:i+1] in wordDict) or (p==0 and s[p:i+1] in wordDict): res[i]=1 break p-=1 return True if res[-1]==1 else False

另：

class Solution: def wordBreak(self, s: str, wordDict: List[str]) -> bool: arr,wordSet=[0],set(wordDict) for i in range(len(s)): for j in arr[::-1]: if s[j:i+1] in wordSet: arr.append(i+1) break return arr[-1]==len(s)

方法二：记忆化回溯

方法三：宽度优先搜索

略

 

转载于:https://www.cnblogs.com/oldby/p/11197397.html

总结

以上是生活随笔为你收集整理的leetcode-139-单词拆分的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。