问题描述

Leetcode 140 是一道关于单词拆分的问题，要求从给定的字符串中找到所有可以通过字典中单词组合而成的子字符串。这个问题的核心在于，我们如何快速、有效地从一个大的字符串中提取出符合条件的单词组合。问题的挑战在于要考虑起始位置和结束位置的组合，确保每个拆分的结果都可以在给定的字典中找到。

想象一下，有一个字符串 "catsanddog" 和一个单词字典 ["cat", "cats", "and", "sand", "dog"]。我们需要找到所有可以通过这些词组合成的子字符串。在这个例子中，解是 ["cats and dog", "cat sand dog"]。这样的题目不仅考验我们的算法思维，也让我们在字典匹配和字符串处理上有了更多的练习。

输入输出格式

输入格式比较简单，首先是个字符串 s，接下来是一个包含若干单词的列表 wordDict。输出是一个列表，包含了所有的有效的组合字符串，每个组合是由空格分开的单词构成。具体来说，输入可以用这样的方式表示：

输入：
s = "catsanddog"
wordDict = ["cat", "cats", "and", "sand", "dog"]

输出：
["cats and dog", "cat sand dog"]

在这里，输入的字符串可以任意长度，而 wordDict 列表的长度也是不定的。输出的格式则是一个数组，其中每个元素都是一种可能的组合。

示例分析

让我们来看看几个样例，深入理解这个题目。假设有如下输入：

s = "applepenapple"
wordDict = ["apple", "pen"]

根据字典中的单词，我们可以构建出“apple pen apple”的组合，其他的组合都无法符合条件。因此，输出将是 ["apple pen apple"]。对于类似的例子，例如输入字符串 "catsanddog" 和字典 ["cat", "cats", "and", "sand", "dog"]，正如之前提到的，得到的有效输出组合都是完全由字典中的单词组成。

这种问题的多样性与复杂性主要在于如何有效地遍历所有可能的拆分点，同时确保组合的唯一性与有效性。动态规划和回溯算法是解决此类问题的常用策略，在下一个章节中，我们将一起探讨这些解题策略的细节和实现方式。

力扣题目策略总览

在面对 Leetcode 140 这个问题时，我们不仅需要理解题目的基本要求，还要明确各种解法以及它们的适用情况。解决这类问题的主要策略有两种：动态规划和回溯。两者各有优缺点，而选择哪一种方法常常取决于具体的场景和限制条件。

动态规划在处理最优子结构和重叠子问题的情况下表现优异。它强大的记忆化机制能显著减少计算重复工作。且通过构建状态转移方程，能够将复杂问题简化为多个简单问题的组合。另一方面，回溯算法则更灵活，适合处理各种组合情况，可通过递归深度优先遍历所有可能的结果。每种策略都值得一试，具体选择还需结合具体的输入数据和性能要求。

动态规划方法

动态规划的基本概念

动态规划是一种通过将问题拆分成更小的子问题来解决更大问题的技术。在 Leetcode 140 题中，我们可以构建一个动态规划数组 dp，使得 dp[i] 表示从字符串的开头到索引 i 的子字符串是否可以由字典中的单词组成。这种方法通过减少重复计算，能够高效地处理较大规模的字符串。

当我第一次接触动态规划时，总是试图找到一个通用的公式来描述状态转移。这在 Leetcode 140 上同样适用，通过确定每个字符的可能拆分点，我们才能逐步构建出答案。

动态规划的状态定义

在定义状态时，我通常会考虑从头到尾遍历字符串的每一个字符，并利用字典中的单词去匹配当前的子字符串。具体地说，设定一个动态规划数组 dp，其中 dp[i] 表示字符串 s 的前 i 个字符是否能由字典中的单词组成。如果字符串的某个前缀可以匹配，并且后续部分也能由字典中的单词组成，那么这个状态就被认定为有效。

通过这种方式构建状态，可以清晰地把问题拆解成更小的部分，一步步推导出最后的结果。这对解决类似的字符串组合问题极为有效。

动态规划的转移方程

一旦确定了状态，我们需要制定转移方程。在这里，我使用的是以下逻辑：dp[i] 为真当且仅当存在一个 j，使得 s[j:i] 在字典中，并且 dp[j] 为真。这意味着当前位置前的部分可以由字典构造出来，随后我们看当前子串是否也能找到合适的词匹配。

这个转移方程的设计使我在设计算法结构时感觉更加清晰，能够以递增的方式检验字符串的每一部分。通过这种结构，可以将整体问题逐步缩小到最小的子问题，最终找到解决方案。

递归与回溯方法

递归的基本思想

另一种解决 Leetcode 140 的方法是使用递归与回溯法。这种方法通过逐步构造解来探索所有可能的组合。初次接触这个方法时，我意识到其灵活性使得解决问题时，可以在不同的路径上尝试并返回，而不必一次次重复计算相同的子问题。

我通常会设计一个递归函数，接收当前的字符串和剩余的词典，生成可能的单词组合。当字符串的某个前缀与字典中的某个单词匹配时，就将其添加到当前组合中，继续对剩余部分进行处理。虽然这种方法直观且易于理解，但在时间复杂度上可能比较昂贵。

适用场景与复杂度分析

递归与回溯在处理这种问题上有其独特的优势，尤其是在组合数目较少时，能够更简单地探索整个解的空间。我发现，通过这种方法能更好地应对一些复杂的输入情况，获得所有可能的组合。然而，需要注意的是，时间复杂度和空间复杂度可能会显著上升，尤其是输入较长时。因此，在实现时要灵活运用剪枝策略，避免不必要的递归调用。

在多种解法中，了解每种方法的优缺点，以及它们在实际应用中的有效性，能帮助我在算法课上更自信地选择合适的策略。各种解法的相互补充使解决 Leetcode 140 变得更加有趣和富有挑战性。 def wordBreak(s: str, wordDict: List[str]) -> List[str]:

word_set = set(wordDict)
dp = [False] * (len(s) + 1)
dp[0] = True
for i in range(1, len(s) + 1):
    for j in range(i):
        if dp[j] and s[j:i] in word_set:
            dp[i] = True
            break

result = []
def backtrack(start: int, path: List[str]):
    if start == len(s):
        result.append(' '.join(path))
        return
    for end in range(start + 1, len(s) + 1):
        if dp[end] and s[start:end] in word_set:
            backtrack(end, path + [s[start:end]])

backtrack(0, [])
return result