如何使用Recursion（递归）求解字符串的最大有效单词拆分数量？

问题描述 #

给定字符串s和有效单词字典d，需要用递归方法确定该字符串能拆分出的最大有效单词数量。比如字符串"warmontheat"最多可拆分为4个单词：warm、on、the、at。我写了下面的代码，但没得到预期结果，想知道怎么用递归解决这个问题。

原代码如下：

def wordBreak( s, wordDict):
    
        if len(s)==0:
            return 0
        for end in range( 1, len(s) + 1):
            if s[0:end] in wordDict and wordBreak(s, wordDict):
                return 1
       
 
        return wordBreak(s, wordDict)

s="warmontheat"
words=("war","month","on","the","heat","eat","he","arm","at","warm")
print(wordBreak(s,words))

原代码问题分析 #

• 递归参数错误：每次递归都传入原字符串s，没有截断处理剩余子串，导致无法推进拆分逻辑，最终陷入无限递归
• 条件判断逻辑错误：wordBreak(s, wordDict)调用的还是原字符串，永远触发不了len(s)==0的base case，判断毫无意义
• 返回值逻辑错误：找到一个匹配的前缀就直接返回1，完全没考虑统计最大单词数量的需求，逻辑完全偏离目标

正确递归实现思路 #

递归的核心是分解子问题：对于当前字符串，尝试所有可能的有效前缀，然后递归计算剩余子串的最大单词数，取所有可能中的最大值。

基础递归版本（无记忆化） #

def max_word_break(s, word_dict):
    # base case：空字符串不需要任何单词，返回0
    if not s:
        return 0
    max_count = -1  # 初始化为-1表示当前子串无法拆分
    # 遍历所有可能的前缀结尾位置
    for end in range(1, len(s)+1):
        prefix = s[:end]
        if prefix in word_dict:
            # 递归处理剩余子串
            rest_count = max_word_break(s[end:], word_dict)
            # 如果剩余子串可以拆分，计算当前总数量
            if rest_count != -1:
                current_count = 1 + rest_count
                # 更新最大数量
                if current_count > max_count:
                    max_count = current_count
    return max_count

s = "warmontheat"
words = {"war","month","on","the","heat","eat","he","arm","at","warm"}
result = max_word_break(s, words)
print(result)  # 输出：4

带记忆化的优化版本 #

上面的基础递归会重复计算大量相同子串的结果，用记忆化缓存可以大幅提升效率：

def max_word_break_memo(s, word_dict, memo=None):
    if memo is None:
        memo = {}
    # 先查缓存，避免重复计算
    if s in memo:
        return memo[s]
    if not s:
        return 0
    max_count = -1
    for end in range(1, len(s)+1):
        prefix = s[:end]
        if prefix in word_dict:
            rest_count = max_word_break_memo(s[end:], word_dict, memo)
            if rest_count != -1:
                current_count = 1 + rest_count
                if current_count > max_count:
                    max_count = current_count
    # 把当前子串的结果存入缓存
    memo[s] = max_count
    return max_count

s = "warmontheat"
words = {"war","month","on","the","heat","eat","he","arm","at","warm"}
result = max_word_break_memo(s, words)
print(result)  # 输出：4

代码说明 #

• Base Case：当字符串为空时，返回0，因为不需要任何单词就能拆分完成
• 遍历前缀：逐个尝试从字符串开头截取不同长度的前缀，检查是否在字典中
• 递归子问题：如果前缀有效，递归处理剩余的子字符串，得到剩余部分的最大单词数
• 更新最大值：如果剩余子串可以拆分，计算当前总数量（1+剩余数量），并更新全局最大数量
• 记忆化优化：用字典缓存已经计算过的子串结果，避免重复计算，提升递归效率

内容的提问来源于stack exchange，提问作者Dogdigger