139. 单词拆分
题目简述:
给你一个字符串 s 和一个字符串列表 wordDict 作为字典。请你判断是否可以利用字典中出现的单词拼接出 s 。
注意:不要求字典中出现的单词全部都使用,并且字典中的单词可以重复使用。
1. 初始化dp=[False,......,False],长度为n+1
2. dp[i]表示s的前i位是否可以用wordDict中的单词表示
3. 初始化dp[0]=True,空字符可以被表示
4. 遍历字符串的所有子串,遍历开始索引i,遍历区间[0,n)
遍历结束索引 j ,遍历区间[i+1,n+1):
若dp[i]=True且s[i,...,j)在wordDict中,则dp[j]=True
代码如下:
class Solution: def wordBreak(self, s: str, wordDict: List[str]) -> bool: n=len(s) dp=[False]*(n+1) dp[0]=True for i in range(n): for j in range(i+1,n+1): if(dp[i] and (s[i:j] in wordDict)): dp[j]=True return dp[-1]