一、问题描述
给你一个字符串 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、思路
动态规划是解决此类问题的常用方法。我们定义一个一维数组 dp[i] 表示字符串 s 的前 i 个字符是否可以被拆分成字典中的单词。
- 初始化
dp[0] = true，因为空字符串可以被拆分成任意单词的空子集。 - 对于每个长度
i，我们需要检查所有可能的拆分点j，如果dp[j]为true并且s[j:i]在字典中，那么dp[i] = true。
2、代码实现
go
func wordBreak(s string, wordDict []string) bool {
wordSet := make(map[string]bool)
for _, word := range wordDict {
wordSet[word] = true
}
dp := make([]bool, len(s)+1)
dp[0] = true
for i := 1; i <= len(s); i++ {
for j := 0; j < i; j++ {
if dp[j] && wordSet[s[j:i]] {
dp[i] = true
break
}
}
}
return dp[len(s)]
}3、复杂度分析
- 时间复杂度：O(n^2)，其中 n 是字符串 s 的长度。我们需要填充一个长度为 n 的一维数组，每次填充需要考虑 n 个可能的拆分点。
- 空间复杂度：O(n)，我们需要一个长度为 n 的一维数组来存储中间结果。
三、方案二：递归 + 记忆化搜索
1、思路
我们可以使用递归的方法来解决这个问题。对于字符串 s 的每个位置 i，我们可以选择将其作为一个单词的结束位置，然后递归地检查剩余的子串是否可以被拆分。为了避免重复计算，我们可以使用一个一维数组来存储已经计算过的结果。
2、代码实现
go
func wordBreak(s string, wordDict []string) bool {
wordSet := make(map[string]bool)
for _, word := range wordDict {
wordSet[word] = true
}
memo := make([]bool, len(s))
var dfs func(start int) bool
dfs = func(start int) bool {
if start == len(s) {
return true
}
if memo[start] {
return false
}
for end := start + 1; end <= len(s); end++ {
if wordSet[s[start:end]] && dfs(end) {
return true
}
}
memo[start] = true
return false
}
return dfs(0)
}3、复杂度分析
- 时间复杂度：O(n^2)，其中 n 是字符串 s 的长度。尽管我们使用了递归，但由于记忆化搜索，每个子问题只被计算一次。
- 空间复杂度：O(n)，我们需要一个长度为 n 的一维数组来存储中间结果。
四、总结
| 方案 | 时间复杂度 | 空间复杂度 | 备注 |
|---|---|---|---|
| 动态规划 | O(n^2) | O(n) | 适合解决此类问题，易于理解和实现 |
| 递归 + 记忆化搜索 | O(n^2) | O(n) | 通过递归实现，代码更简洁，但可能不如动态规划直观 |
| 两种方案在时间和空间复杂度 |