139. 单词拆分 #

链接 #

139. 单词拆分

题目 #

给你一个字符串 s 和一个字符串列表 wordDict 作为字典。如果可以利用字典中出现的一个或多个单词拼接出 s 则返回 true。

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

示例 1：

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

示例 2：

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

示例 3：

输入: s = "catsandog", wordDict = ["cats", "dog", "sand", "and", "cat"]
输出: false

提示：

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

解答 #

这道题的思路是使用动态规划。我们定义一个布尔数组 dp，其中 dp[i] 表示字符串 s 的前 i 个字符是否可以被拆分成字典 wordDict 中的单词。数组的长度为 len(s) + 1，初始化 dp[0] 为 True，因为一个空字符串总是可以被拆分（即不使用任何单词）。

接下来，我们遍历字符串 s 的每一个字符，对于每个位置 i，我们再次遍历从 0 到 i-1 的所有位置 j。如果 dp[j] 为 True，说明字符串 s 的前 j 个字符可以被拆分，那么我们检查从位置 j 到 i 的子串 s[j:i] 是否在字典 wordDict 中。如果在，说明从位置 j 到 i 的子串可以被拆分成一个单词，因此 dp[i] 也为 True。 如果在某个位置 i 处，我们找到了一个 j 使得 dp[j] 为 True 并且 s[j:i] 在字典中，我们就将 dp[i] 设置为 True 并中断当前循环，因为一旦找到一个拆分方式，就没有必要继续检查其他位置了。 最后，dp[len(s)] 的值就是我们要找的答案，它表示整个字符串 s 是否可以被拆分成字典中的单词。 这种方法的时间复杂度是 O(n^2)，其中 n 是字符串 s 的长度。空间复杂度是 O(n)，用于存储动态规划数组。

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