DSA Interview Prep · 课时

单词拆分与字符串分段

Q: 「单词拆分与字符串分段」课时是免费的吗？

是的 — 「单词拆分与字符串分段」的完整文本可在网页上免费阅读。要进行交互式练习（内置代码编辑器和全天候 AI 导师）并解锁 DSA Interview Prep 课程的其余内容，请升级到 CoddyKit PRO。 DSA Interview Prep 课程共包含 4 节课。

Q: 「单词拆分与字符串分段」这节课中我会学到什么？

使用一维 DP 表判断字符串能否拆分为字典中的单词，分析 O(n²) 的时间复杂度，并了解字典树如何加速。 你通过在浏览器中直接运行的动手代码来练习 DSA Interview Prep，全天候 AI 导师会在你学习这节课的过程中回答你的问题。

Q: 学习 DSA Interview Prep 需要有经验吗？

无需任何先前经验。CoddyKit 上的 DSA Interview Prep 课程适合初学者到高级学习者，你可以从这里开始或从头开始，按照自己的节奏学习。 这是第 3 节课，共 4 节。

Q: 「单词拆分与字符串分段」课时需要多长时间？

大多数 CoddyKit 课程大约需要 5–10 分钟。每节课都很精短且互动，所以你能稳步进步，并在网页和应用中从离开的地方继续。

Q: 我能在这节 DSA Interview Prep 课中编写并运行代码吗？

能。每节 DSA Interview Prep 课都包含内置代码编辑器，你可以在浏览器中直接编写并运行真实代码，并获得即时 AI 反馈 — 无需本地设置。

使用一维 DP 表判断字符串能否拆分为字典中的单词，分析 O(n²) 的时间复杂度，并了解字典树如何加速。

单词拆分与字符串分段 是 CoddyKit 上的免费 DSA Interview Prep 课时。这是第 3 节课，共 4 节。你可以在下方免费阅读本课时的完整内容 — 然后在浏览器中使用内置代码编辑器和全天候 AI 导师进行实践。这是 DSA Interview Prep 学习路径的一部分，你的进度在网页和 CoddyKit 应用中同步。 DSA Interview Prep 课程共包含 4 节课。

单词拆分问题

单词拆分（LeetCode 139）要求：给定字符串 s 和一个单词字典，判断 s 是否可以拆分为由空格分隔的一个或多个字典单词。例如，对于 s = 'leetcode' 和 wordDict = ['leet', 'code']，答案是 True，因为 'leet' + 'code' = 'leetcode'。这是一个经典的一维 DP 问题。

s = 'leetcode'
word_set = {'leet', 'code'}
# Can we split 'leetcode' into words from word_set?
# 'leet' in set → yes, 'code' in set → yes
# So: 'leetcode' = 'leet' + 'code' → True

s2 = 'catsandog'
word_set2 = {'cats', 'dog', 'sand', 'and', 'cat'}
# No matter how we split, last part 'og' not in dict
print('Expected: True, False')

DP 形式化定义与状态

将 dp[i] 定义为：如果子字符串 s[:i] 可以使用字典进行拆分，则为 True。基本情况是 dp[0] = True（空字符串始终可以拆分）。对于每个位置 i，检查所有满足 j < i 的位置：如果 dp[j] 为真，且 s[j:i] 在字典中，则令 dp[i] = True。最终答案是 dp[len(s)]。

def word_break(s, word_dict):
    word_set = set(word_dict)
    n = len(s)
    dp = [False] * (n + 1)
    dp[0] = True  # empty string
    
    for i in range(1, n + 1):
        for j in range(i):
            # If s[:j] is segmentable AND s[j:i] is a word
            if dp[j] and s[j:i] in word_set:
                dp[i] = True
                break  # no need to check other j values
    return dp[n]

print(word_break('leetcode', ['leet', 'code']))        # True
print(word_break('catsandog', ['cats','dog','sand','and','cat']))  # False

跟踪 DP 表

对于 s = 'leetcode' 和字典 {'leet', 'code'}：dp[0]=T。在 i=4 时：j=0，dp[0]=T 且 s[0:4]='leet' 属于字典 → dp[4]=T。在 i=8 时：j=4，dp[4]=T 且 s[4:8]='code' 属于字典 → dp[8]=T。其他没有单词结束的位置都保持为 False。答案 dp[8]=True 确认该字符串可以拆分。

def word_break_trace(s, word_dict):
    word_set = set(word_dict)
    n = len(s)
    dp = [False] * (n + 1)
    dp[0] = True
    for i in range(1, n + 1):
        for j in range(i):
            if dp[j] and s[j:i] in word_set:
                dp[i] = True
                print(f'dp[{i}]=True via s[{j}:{i}]={repr(s[j:i])}')
                break
    print('dp table:', dp)
    return dp[n]

word_break_trace('leetcode', ['leet', 'code'])

时间复杂度分析

朴素 DP 的运行时间为O(n²)：外层循环执行 n 次，每次最多执行 n 次内层循环。不过，对 s[j:i] 进行切片也需要 O(n) 的开销，因此在 Python 中实际复杂度为O(n³)。一种优化方法是遍历字典中的单词，并检查每个单词是否在位置 i 处结束，这样复杂度为 O(n × W × L)，其中 W 是字典大小，L 是平均单词长度。对于大多数面试输入，O(n²) 或 O(n³) 都可以接受。

# Slightly faster: iterate over words rather than all j positions
def word_break_v2(s, word_dict):
    word_set = set(word_dict)
    n = len(s)
    dp = [False] * (n + 1)
    dp[0] = True
    for i in range(1, n + 1):
        for word in word_set:
            wl = len(word)
            # Does 'word' end exactly at position i?
            if i >= wl and dp[i - wl] and s[i - wl:i] == word:
                dp[i] = True
                break
    return dp[n]

print(word_break_v2('applepenapple', ['apple', 'pen']))  # True

记忆化递归替代方案

同一个问题也可以使用记忆化自顶向下解决。定义递归函数 can_break(start)：如果 s[start:] 可以拆分，则返回真。将每个单词作为 s[start:] 的前缀进行尝试，并对剩余部分递归处理。缓存结果，避免多次重新探索同一个起始索引。这与自底向上的 DP 等价，但如果许多位置能够较早被剪枝，实际运行可能更快。

from functools import lru_cache

def word_break_memo(s, word_dict):
    word_set = set(word_dict)
    
    @lru_cache(maxsize=None)
    def can_break(start):
        if start == len(s): return True
        for end in range(start + 1, len(s) + 1):
            if s[start:end] in word_set and can_break(end):
                return True
        return False
    
    return can_break(0)

print(word_break_memo('leetcode', ['leet', 'code']))  # True
print(word_break_memo('catsandog', ['cats','dog','sand','and','cat']))  # False

返回所有有效拆分

单词拆分 II（LeetCode 140）要求返回所有可能的拆分方式。方法是结合回溯与记忆化：从每个位置递归处理，匹配到单词后再对剩余部分递归。将所有部分结果存储为字符串列表。为了避免 TLE，请记忆化存储从每个起始索引开始可能得到的句子列表。句子数量在最坏情况下可能呈指数级增长，但记忆化可以消除重复计算。

from functools import lru_cache

def word_break_ii(s, word_dict):
    word_set = set(word_dict)
    
    @lru_cache(maxsize=None)
    def break_from(start):
        if start == len(s): return ['']
        results = []
        for end in range(start + 1, len(s) + 1):
            word = s[start:end]
            if word in word_set:
                for rest in break_from(end):
                    results.append(word if not rest else word + ' ' + rest)
        return results
    
    return break_from(0)

print(word_break_ii('catsanddog', ['cat','cats','and','sand','dog']))
# ['cat sand dog', 'cats and dog']

前缀树优化

当字典很大或单词很长时，由于编程语言的字符串哈希机制，对所有 j 检查 s[j:i] in word_set 会很慢。前缀树允许您逐字符遍历树，并尽早剪掉不可能的路径。您不必检查全部 O(n) 个起始位置，而只需沿着前缀树中存在的路径前进。当很少有前缀能形成有效单词时，这种方法可以显著降低实际运行时间。

class TrieNode:
    def __init__(self):
        self.children = {}
        self.is_end = False

def build_trie(words):
    root = TrieNode()
    for word in words:
        node = root
        for ch in word:
            node = node.children.setdefault(ch, TrieNode())
        node.is_end = True
    return root

def word_break_trie(s, word_dict):
    root = build_trie(word_dict)
    n = len(s)
    dp = [False] * (n + 1)
    dp[0] = True
    for i in range(n):
        if not dp[i]: continue
        node = root
        for j in range(i, n):
            ch = s[j]
            if ch not in node.children: break
            node = node.children[ch]
            if node.is_end:
                dp[j + 1] = True
    return dp[n]

print(word_break_trie('leetcode', ['leet', 'code']))  # True

边界情况与约束

重要的边界情况：(1) 空字符串：返回 True（空字符串显然可以拆分）。(2) 单词不在字典中：DP 永远不会将对应位置设为 True，因此会正确返回 False。(3) 重叠单词：例如，字典中有 'a' 和 'aa'，且 s='aaa'——DP 会通过检查所有 j 值自然地处理这种情况。(4) 重复字符：s='aaaaab'，字典为 ['a','aa','aaa']——路径数量呈指数级增长，但记忆化会将复杂度限制在 O(n²)。

def word_break(s, word_dict):
    word_set = set(word_dict)
    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
    return dp[len(s)]

# Edge cases
print(word_break('', ['hello']))          # True (empty string)
print(word_break('a', ['b']))             # False
print(word_break('aaa', ['a', 'aa']))     # True (many ways)

字符串拆分的泛化

单词拆分可以泛化到任何字符串拆分问题：字符串 s 是否可以按照某种规则进行分割？将字典查找替换为任何 O(1) 或 O(L) 的检查即可。例如：s 是否可以拆分成回文串？此时可以使用预先计算的回文表，而不是单词集合。DP 结构完全相同——只有有效性检查会发生变化。

def palindrome_partition_possible(s):
    '''Can s be partitioned into palindromes? (Always yes — single chars are palindromes)'''
    n = len(s)
    # Precompute palindrome table
    is_pal = [[False]*n for _ in range(n)]
    for i in range(n): is_pal[i][i] = True
    for i in range(n-1): is_pal[i][i+1] = (s[i]==s[i+1])
    for length in range(3, n+1):
        for i in range(n-length+1):
            j = i + length - 1
            is_pal[i][j] = s[i]==s[j] and is_pal[i+1][j-1]
    # DP similar to word break
    dp = [False] * (n + 1)
    dp[0] = True
    for i in range(1, n + 1):
        for j in range(i):
            if dp[j] and is_pal[j][i-1]:
                dp[i] = True
                break
    return dp[n]

print(palindrome_partition_possible('aab'))  # True (a,a,b or aa,b)

DP 与 BFS 方法

单词拆分也可以表述为BFS 最短路径问题：字符串中的每个位置都是一个节点，如果 s[j:i] 在字典中，则从 j 到 i 存在一条边。从节点 0 开始执行 BFS，就是要判断节点 n 是否可达。BFS 的复杂度同样为 O(n² × L)，但如果您在面试中将其建模为图问题，这种方法可能更直观。

from collections import deque

def word_break_bfs(s, word_dict):
    word_set = set(word_dict)
    n = len(s)
    visited = set()
    queue = deque([0])
    while queue:
        start = queue.popleft()
        if start == n: return True
        for end in range(start + 1, n + 1):
            if end not in visited and s[start:end] in word_set:
                visited.add(end)
                queue.append(end)
    return False

print(word_break_bfs('leetcode', ['leet', 'code']))    # True
print(word_break_bfs('catsandog', ['cats','dog','and','sand','cat']))  # False

面试沟通策略

在面试中，请按以下思路进行讲解：(1) 注意到每个位置的选择取决于之前哪些位置可达——这表明应使用 DP。(2) 定义状态：dp[i] = s[:i] 是否可以拆分？(3) 在编写代码前先说明递推式和基本情况。(4) 先编写 O(n²) 解决方案，然后将前缀树优化作为后续改进方案提及。(5) 讨论边界情况：空字符串、单个字符、单词不在字典中。

# Clean final solution to present in interview
def word_break(s, word_dict):
    '''O(n^2 * L) time, O(n + W) space where W = total word length in dict'''
    word_set = set(word_dict)   # O(W) space
    n = len(s)
    dp = [False] * (n + 1)     # O(n) space
    dp[0] = True
    for i in range(1, n + 1):
        for j in range(i):     # try all split points
            if dp[j] and s[j:i] in word_set:
                dp[i] = True
                break
    return dp[n]

# Time: O(n^2 * L) - n^2 pairs, each dict lookup is O(L)
# Space: O(n) for dp array, O(W) for word_set
print(word_break('applepenapple', ['apple', 'pen']))  # True

快速检查

请检验您对本课中数据结构与算法——编程面试准备相关概念的理解。

课程回顾

在本课中，您学到了：dp[i] 表示 s[:i] 是否可以拆分成字典单词、O(n²) 递推式会检查所有满足 dp[j]=True 且 s[j:i] 属于单词集合的切分点 j，以及前缀树可以通过尽早剪掉不存在的前缀来加速内层循环。接下来，我们将探索解码方法和路径计数，这是另一种类似斐波那契数列的一维 DP 模式。

常见问题解答