线性动态规划：单词拆分

让我为您讲解单词拆分（Word Break）这个线性动态规划问题。

题目描述
给定一个非空字符串s和一个包含非空单词列表的字典wordDict，判断s是否可以被拆分成一个或多个字典中单词的空格分隔序列。注意，字典中的单词可以重复使用，且不限制使用次数。

示例：
输入：s = "leetcode", wordDict = ["leet", "code"]
输出：true
解释："leetcode" 可以拆分为 "leet code"

解题思路
这是一个典型的线性动态规划问题，我们可以使用动态规划来判断从开头到每个位置是否可以被成功拆分。

详细解题步骤

步骤1：定义状态
定义dp[i]表示字符串s的前i个字符（即s[0:i]）是否可以被拆分成字典中的单词。

步骤2：状态转移方程
对于每个位置i（从1到n），我们需要检查所有可能的分割点j（0 ≤ j < i）：

• 如果dp[j]为true（表示前j个字符可以被拆分）
• 并且子串s[j:i]在字典中
  那么dp[i] = true

状态转移方程可以表示为：
dp[i] = dp[j] && (s[j:i] ∈ wordDict)，对于某个j ∈ [0, i)

步骤3：初始化
dp[0] = true，表示空字符串可以被拆分（作为递归的基准情况）

步骤4：算法实现

def wordBreak(s, wordDict):
    n = len(s)
    # 将字典转换为集合，提高查找效率
    wordSet = set(wordDict)
    
    # 初始化dp数组
    dp = [False] * (n + 1)
    dp[0] = True  # 空字符串可以被拆分
    
    # 填充dp数组
    for i in range(1, n + 1):
        for j in range(i):
            # 如果前j个字符可以被拆分，且s[j:i]在字典中
            if dp[j] and s[j:i] in wordSet:
                dp[i] = True
                break  # 找到一个有效的拆分方式即可
    
    return dp[n]

步骤5：详细示例分析
以s = "leetcode", wordDict = ["leet", "code"]为例：

初始化：dp = [True, False, False, False, False, False, False, False, False]

i=1: 检查"l"是否在字典中 → 不在
i=2: 检查"le"是否在字典中 → 不在
i=3: 检查"lee"是否在字典中 → 不在
i=4:

• j=0: dp[0]=True, "leet"在字典中 → dp[4]=True
  i=5: 检查"c"是否在字典中 → 不在
  i=6: 检查"co"是否在字典中 → 不在
  i=7: 检查"cod"是否在字典中 → 不在
  i=8:
• j=4: dp[4]=True, "code"在字典中 → dp[8]=True

最终结果：dp[8] = True

步骤6：时间复杂度优化
上面的解法时间复杂度为O(n²)，我们可以进行优化：

• 只遍历到最大单词长度，避免不必要的检查
• 提前检查字典中单词的最大长度

优化后的代码：

def wordBreak(s, wordDict):
    n = len(s)
    wordSet = set(wordDict)
    max_len = max(len(word) for word in wordDict) if wordDict else 0
    
    dp = [False] * (n + 1)
    dp[0] = True
    
    for i in range(1, n + 1):
        # 只检查可能的分割点，避免不必要的循环
        for j in range(max(0, i - max_len), i):
            if dp[j] and s[j:i] in wordSet:
                dp[i] = True
                break
    
    return dp[n]

步骤7：边界情况考虑

1. 空字符串：应该返回True
2. 字典为空：除非字符串也为空，否则返回False
3. 字典中有重复单词：使用集合自动去重
4. 字典中的单词比字符串长：不会影响结果

这个算法清晰地展示了如何使用动态规划解决字符串拆分问题，通过记录每个位置的可拆分性，最终得到整个字符串的可拆分性判断。