力扣-单词拆分

🔗 题目链接

给你一个字符串 s 和一个字符串列表 wordDict 作为字典。请你判断是否可以利用字典中出现的单词拼接出 s。

注意：不要求字典中出现的单词全部都使用，并且字典中的单词可以重复使用。

提示：

• $1 <= s.length <= 300$
• $1 <= wordDict.length <= 1000$
• $1 <= wordDict[i].length <= 20$
• s 和 wordDict[i] 仅有小写英文字母组成
• wordDict 中的所有字符串互不相同

动态规划+记忆化回溯 逐行解释 python3¹

动态规划

1. 初始化 $dp=[False,⋯,False]$，长度为 $n+1$。$n$ 为字符串长度。$dp[i]$ 表示 $s$ 的前 $i$ 位是否可以用 $wordDict$ 中的单词表示。
2. 初始化 $dp[0]=True$，空字符可以被表示。
3. 遍历字符串的所有子串，遍历开始索引 $i$，遍历区间 $[0,n)$：
   • 遍历结束索引 $j$，遍历区间 $[i+1,n+1)$：
     • 若 $dp[i]=True$ 且 $s[i,⋯,j)$ 在 $wordlistword$ 中：$dp[j]=True$。解释：$dp[i]=True$ 说明 $s$ 的前 $i$ 位可以用 $wordDict$ 表示，则 $s[i,⋯,j)$ 出现在 $wordDict$ 中，说明 $s$ 的前 $j$ 位可以表示。
4. 返回 $dp[n]$

代码

1
2
3
4
5
6
7
8
9

def wordBreak(s, wordDict):
    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]

复杂度分析

• 时间复杂度：$O(n^{2})$
• 空间复杂度：$O(n)$