线性动态规划：单词拆分 题目描述 给定一个非空字符串 s 和一个包含非空单词列表的字典 wordDict ，判断 s 是否可以被拆分为一个或多个字典中单词的空格分隔序列。同一个单词可以被重复使用，字典中的单词不重复。 示例 输入：s = "leetcode", wordDict = [ "leet", "code" ] 输出：true 解释："leetcode" 可以拆分为 "leet" 和 "code"。 解题思路 定义状态 ：设 dp[i] 表示字符串 s 的前 i 个字符（即 s[0:i] ）能否被拆分成字典中的单词。 状态转移 ：对于每个位置 i （从 1 到 n ），检查所有可能的拆分点 j （0 ≤ j < i），若 dp[j] 为真且子串 s[j:i] 在字典中，则 dp[i] = true 。 初始条件 ： dp[0] = true ，表示空字符串默认可拆分。 最终结果 ： dp[n] 的值即为整个字符串 s 是否可拆分。 详细步骤 初始化长度为 n+1 的布尔数组 dp ，全部设为 false ， dp[0] = true 。 将 wordDict 转换为哈希集合 wordSet 以便快速查询。 外层循环遍历 i 从 1 到 n （对应子串 s[0:i] ）： 内层循环遍历 j 从 0 到 i-1 ： 若 dp[j] 为真且 s.substring(j, i) 在 wordSet 中，则设置 dp[i] = true 并跳出内层循环（无需继续检查其他 j ）。 返回 dp[n] 。 示例推导 （s = "leetcode", wordDict = [ "leet", "code" ]） dp[0] = true （空字符串） i=4 ：检查 j=0 ， dp[0]=true 且 "leet" 在字典中 → dp[4]=true i=8 ：检查 j=4 ， dp[4]=true 且 "code" 在字典中 → dp[8]=true 最终 dp[8] 为 true，字符串可拆分。 复杂度分析 时间复杂度：O(n²)，其中 n 为字符串长度。 空间复杂度：O(n) 用于存储 dp 数组和哈希集合。