解题思路
动态规划
如果前一个点结束的串是可以切分的，并且从那个点到目前的位置的子串在字典里，当前节点之前的串就是可以切分的
139. 单词拆分
代码
class Solution:
def wordBreak(self, s: str, wordDict: List[str]) -> bool:
N = len(s)
word_set = set(wordDict)
dp = [True] + [False for c in s] # dp[0] == True
index = 1
while index <= N:
for left in range(index-1, -1, -1):
if dp[left] and s[left:index] in word_set:
dp[index] = True
break
index += 1
return dp[N]
效果图
网友评论