一、问题描述

给定一个非空字符串 s 和一个包含非空单词的列表 wordDict，判定 s 是否可以被空格拆分为一个或多个在字典中出现的单词。 说明：

• 拆分时可以重复使用字典中的单词。
• 你可以假设字典中没有重复的单词。

二、方案一：记忆化搜索（DFS + Memoization）

1、思路

我们可以使用深度优先搜索（DFS）来解决这个问题。从字符串的起始位置开始，我们尝试使用字典中的每个单词来拆分字符串，并递归地检查剩余部分是否可以被拆分。为了避免重复计算，我们可以使用记忆化搜索，即使用一个数组来存储已经计算过的子问题的结果。

2、代码实现

func wordBreak(s string, wordDict []string) bool {
    // 将单词字典存储在哈希集合中，以便快速查找
    wordSet := make(map[string]bool)
    for _, word := range wordDict {
        wordSet[word] = true
    }
    // 初始化记忆化数组
    memo := make([]bool, len(s)+1)
    for i := range memo {
        memo[i] = false
    }
    // 定义记忆化搜索函数
    var dfs func(start int) bool
    dfs = func(start int) bool {
        // 如果已经搜索过这个子问题，直接返回结果
        if memo[start] {
            return memo[start]
        }
        // 如果到达字符串末尾，返回 true
        if start == len(s) {
            return true
        }
        // 尝试使用字典中的每个单词来拆分字符串
        for end := start + 1; end <= len(s); end++ {
            if wordSet[s[start:end]] && dfs(end) {
                memo[start] = true
                return true
            }
        }
        // 如果无法拆分，返回 false
        memo[start] = false
        return false
    }
    // 从字符串起始位置开始搜索
    return dfs(0)
}

3、复杂度分析

• 时间复杂度：O(n^2)，其中 n 是字符串 s 的长度。在最坏的情况下，我们需要对每个子字符串调用 dfs 函数，而每个 dfs 函数的时间复杂度是 O(n)。
• 空间复杂度：O(n)，因为我们需要存储记忆化数组和递归调用栈。

三、方案二：动态规划

1、思路

动态规划方法是基于这样一个事实：如果我们知道字符串 s 的前 i 个字符可以被拆分为单词字典中的单词，那么我们可以通过检查 s[i:j] 是否在单词字典中来判断整个字符串是否可以被拆分。 我们可以使用一个数组 dp，其中 dp[i] 表示字符串 s 的前 i 个字符是否可以被拆分为单词字典中的单词。我们初始化 dp[0] = true，然后对于每个 i，我们尝试拆分字符串并更新 dp[i]。

2、代码实现

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 的长度。我们需要计算每个 dp[i] 的值，对于每个 i，我们可能需要遍历整个字符串来检查是否存在有效的拆分。
• 空间复杂度：O(n)，因为我们需要存储动态规划数组。

四、总结

方案	时间复杂度	空间复杂度	备注
记忆化搜索	O(n^2)	O(n)	适用于字符串长度不是特别大的情况
动态规划	O(n^2)	O(n)	适用于字符串长度较大的情况
根据字符串长度和单词字典的大小，我们可以选择合适的方案来解决这个问题。