0139. 单词拆分 #

• 标签：字典树、记忆化搜索、哈希表、字符串、动态规划
• 难度：中等

题目大意 #

描述：给定一个非空字符串 s 和一个包含非空单词的列表 wordDict 作为字典。

要求：判断是否可以利用字典中出现的单词拼接出 s 。

说明：

• 不要求字典中出现的单词全部都使用，并且字典中的单词可以重复使用。
• $1 \le s.length \le 300$。
• $1 \le wordDict.length \le 1000$。
• $1 \le wordDict[i].length \le 20$。
• s 和 wordDict[i] 仅有小写英文字母组成。
• wordDict 中的所有字符串互不相同。

示例：

• 示例 1：

1
2
3

输入: s = "leetcode", wordDict = ["leet", "code"]
输出: true
解释: 返回 true 因为 "leetcode" 可以由 "leet" 和 "code" 拼接成。

• 示例 2：

1
2
3
4

输入: s = "applepenapple", wordDict = ["apple", "pen"]
输出: true
解释: 返回 true 因为 "applepenapple" 可以由 "apple" "pen" "apple" 拼接成。
     注意，你可以重复使用字典中的单词。

解题思路 #

思路 1：动态规划 #

1. 划分阶段 #

按照单词结尾位置进行阶段划分。

2. 定义状态 #

s 能否拆分为单词表的单词，可以分解为：

• 前 $i$ 个字符构成的字符串，能否分解为单词。
• 剩余字符串，能否分解为单词。

定义状态 dp[i] 表示：长度为 $i$ 的字符串 s[0: i] 能否拆分成单词，如果为 True 则表示可以拆分，如果为 False 则表示不能拆分。

3. 状态转移方程 #

• 如果 s[0: j] 可以拆分为单词（即 dp[j] == True），并且字符串 s[j: i] 出现在字典中，则 dp[i] = True。
• 如果 s[0: j] 不可以拆分为单词（即 dp[j] == False），或者字符串 s[j: i] 没有出现在字典中，则 dp[i] = False。

4. 初始条件 #

• 长度为 $0$ 的字符串 s[0: i] 可以拆分为单词，即 dp[0] = True。

5. 最终结果 #

根据我们之前定义的状态，dp[i] 表示：长度为 $i$ 的字符串 s[0: i] 能否拆分成单词。则最终结果为 dp[size]，size 为字符串长度。

思路 1：代码 #

 1
 2
 3
 4
 5
 6
 7
 8
 9
10

class Solution:
    def wordBreak(self, s: str, wordDict: List[str]) -> bool:
        size = len(s)
        dp = [False for _ in range(size + 1)]
        dp[0] = True
        for i in range(size + 1):
            for j in range(i):
                if dp[j] and s[j: i] in wordDict:
                    dp[i] = True
        return dp[size]

思路 1：复杂度分析 #

• 时间复杂度：$O(n^2)$，其中 $n$ 为字符串 s 的长度。
• 空间复杂度：$O(n)$。