Day 46 | 139. Word Break | Backpack Question Summary

**Day46 |139. Word Break | Backpack**

**问题概述**

在本题中，我们将使用背包算法（Backpack）来解决一个单词分割的问题。给定一个字符串 `s` 和一个集合 `wordDict`，我们需要判断是否可以将 `s` 分割成由 `wordDict` 中的单词组成的序列。

**问题描述**

给定一个字符串 `s` 和一个集合 `wordDict`，其中包含一组有效单词。请设计一个算法来判断是否可以将 `s` 分割成由 `wordDict` 中的单词组成的序列。

**示例1**
输入：`s = "leetcode"`, `wordDict = ["leet", "code"]`
输出：`True`

**示例2**
输入：`s = "applepenapple"`, `wordDict = ["apple", "pen"]`
输出：`True`

**示例3**
输入：`s = "catsandog"`, `wordDict = ["cats", "dog", "sand", "and", "cat"]`
输出：`False`

**解决方案**

我们将使用背包算法来解决这个问题。背包算法是一种动态规划的方法，用于求解一个子集的问题。

def wordBreak(s, wordDict):
 n = len(s)
 dp = [False] * (n +1) # dp[i] 表示 s[:i+1] 是否可以分割成由 wordDict 中的单词组成的序列 # 初始化 dp[0] 为 True dp[0] = True for i in range(1, n +1):
 for j in range(i):
 if dp[j] and s[j:i] in wordDict:
 dp[i] = True break return dp[n]

**代码注释**

* `dp` 是一个长度为 `n+1` 的列表，用于存储每个前缀 `s[:i+1]` 是否可以分割成由 `wordDict` 中的单词组成的序列。
* 初始化 `dp[0]` 为 `True`，因为空字符串可以视为已经分割好的序列。
* 遍历每个前缀 `s[:i+1]`，检查是否有任何子串 `s[j:i]` 在 `wordDict` 中，并且 `dp[j]` 为 `True`。如果找到这样的子串，则将 `dp[i]` 置为 `True`。
* 最后返回 `dp[n]` 的值，即整个字符串 `s` 是否可以分割成由 `wordDict` 中的单词组成的序列。

**时间复杂度**

该算法的时间复杂度为 O(n^2)，其中 n 是输入字符串 `s` 的长度。原因是我们需要遍历每个前缀 `s[:i+1]`，并且在每次迭代中，我们可能会检查多达 i 个子串。

**空间复杂度**

该算法的空间复杂度为 O(n)，因为我们需要存储长度为 n+1 的列表 `dp`。