本文共 936 字，大约阅读时间需要 3 分钟。

判断字符串是否能拆分为字典中的单词

给定一个非空字符串s和一个包含非空单词的列表wordDict，目标是判断s是否可以通过拆分为空格分隔的单词列表，其中每个单词都来自wordDict。拆分时允许重复使用字典中的单词。

动态规划方法

我们可以使用动态规划来解决这个问题。动态规划是一种有效的算法设计方法，它通过将大问题分解为多个小问题来解决复杂问题。对于这个问题，动态规划的核心思想是使用一个数组dp来记录子问题的解。

定义dp数组

• dp[i] 表示从字符串的开头到位置i（不包括位置i）是否可以拆分成一个或多个字典中的单词。
• 初始化dp[0]为true，因为空字符串可以被视为一个有效的拆分。

逐步求解

优化点

• 转换字典为集合：为了提升查询效率，将字典转换为集合，这样检查子串是否存在的时间复杂度从O(n)变为O(1)。
• 提前终止：一旦找到一个有效的拆分，立即设定dp[i]为true并终止内层循环，减少不必要的计算。
• 复杂度分析：时间复杂度为O(n*m)，其中n是字符串长度，m是字典中最长单词的长度。空间复杂度为O(n)，可以通过记录仅需的前一行来优化为O(m)。

示例分析

• 示例1：s = "leetcode"，wordDict = ["leet", "code"]。输出true，因为可以拆分为"leet code"。
• 示例2：s = "applepenapple"，wordDict = ["apple", "pen"]。输出true，可以拆分为"apple pen apple"。
• 示例3：s = "catsandog"，wordDict = ["cats", "dog", "sand", "and", "cat"]。输出false，无法找到有效的拆分。

结论

通过动态规划，我们可以高效地判断字符串是否能被拆分为字典中的单词。这种方法不仅保证了正确性，还通过优化手段提升了性能，适用于处理较长的字符串和较大的字典。