题目链接
题目描述
实现代码
动态规划思想:记dp[i]表示在字符串的前i个字符时是否能够进行单词拆分;
对于一个长度为i的字符串,能否被已知的几个字符串组合,就看它每个切分点切分后的子串是否在已知的字符串列表中,遍历字符串,每个点都做为切分点,判定字符串能被拆分需要同时满足下列两个条件:
- 切分点j的前j个字符组成的字符串能被正确拆分;
- 切分点j的后j到i的字符组成的字符串存在于一直的字符串列表中;
实现代码如下:
class Solution:
def wordBreak(self, s: str, wordDict: List[str]) -> bool:
n = len(s)
dp = [True] + [False for _ in range(n)]
for i in range(1, n+1):
for j in range(0, i):
if dp[j]:
sub = s[j:i]
if sub in wordDict:
dp[i] = True
break
return dp[n]