字符串分割为最大数量有效单词问题及代码调试求助

给定字符串s和有效单词字典d，需要确定该字符串能分割成的最大有效单词数量。以下是我尝试的代码，但未得到预期结果：

def word_split_dp(s):
    n = len(s)
    ans = [0]*n
    # base case
    ans[0] = 0
    for i in range(1, len(s)):
        ans[i] = float('-inf')
        for j in range(1, i-1):
            ans[i]= max(ans[i], ans[i-j] + wordcheck(s,i,j))
   
    print(ans)
    return ans[n-2]
       
def wordcheck(s,i,j):
    
    for word in dict:
        start = i-j+1
        if(s[start:i] == word):
            return 1
        else:
            return float('-inf')
        

print(word_split_dp(s))

代码问题分析 #

• 参数传递缺失：word_split_dp未接收字典参数，wordcheck直接使用全局dict，导致无法传入自定义的有效单词字典。
• 索引逻辑错误：
  • ans数组长度为n，但返回ans[n-2]，对应字符串倒数第二个位置的状态，不符合“整个字符串的最大单词数”需求。
  • j的循环范围range(1, i-1)会导致i≤2时循环直接跳过，无法检查所有可能的分割点。
• 单词检查逻辑错误：wordcheck中第一个单词不匹配就直接返回-inf，未遍历完所有字典单词就终止判断，会漏掉匹配的可能。
• DP状态定义不合理：ans[i]定义为第i个字符位置的状态，不如定义dp[i]为前i个字符的最大有效单词数直观，容易混淆索引对应关系。

修正后的代码 #

def max_word_split(s, word_dict):
    n = len(s)
    # dp[i] 表示前i个字符能分割出的最大有效单词数
    dp = [float('-inf')] * (n + 1)
    dp[0] = 0  # 空字符串的单词数为0
    
    for i in range(1, n + 1):
        # 遍历所有可能的分割点j
        for j in range(i):
            if dp[j] != float('-inf') and s[j:i] in word_dict:
                dp[i] = max(dp[i], dp[j] + 1)
    
    # 无法分割时返回0，可根据需求调整
    return dp[n] if dp[n] != float('-inf') else 0

# 示例调用
s = "leetcode"
word_dict = {"leet", "code", "lee", "t"}
print(max_word_split(s, word_dict))  # 输出：3（分割为"lee"+"t"+"code"）

修正说明 #

• 调整DP数组定义：dp[i]对应前i个字符的状态，dp[0]初始化为0（空字符串的基准情况）。
• 遍历所有分割点：对于每个i，检查所有j从0到i-1，若s[j:i]在字典中且dp[j]是可达状态，就更新dp[i]为更大值。
• 简化单词检查：直接用in操作符判断子串是否在字典中，避免错误的循环判断。
• 处理无法分割的情况：若最终dp[n]仍为-inf，说明字符串无法分割为有效单词，返回0。

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