动态规划实现单词拆分组合：二维列表追加错误排查

问题描述 #

实现动态规划算法，判断能否用给定子单词列表重构目标单词，若可行返回所有拆分组合，否则返回空列表。当前算法逻辑方向正确，但结果累积时出错：返回的List<List<string>>中每个子列表仅含单个单词，未正确实现组合的追加，而是覆盖了原有结果。

原始代码 #

List<string> wordbank = new List<string>() { "purp", "p", "ur", "le", "purpl" };
string target = "purple";
Dictionary<int, List<List<string>>> table = new();

for (int i = 0; i < target.Length + 1; i++)
{
    table[i] = new();
}

table[0] = new ();


for (int i = 0; i <= target.Length; i++)
{  
    foreach (var word in wordbank)
    {
        try
        {
            if (target.Substring(i, word.Length) == word)
            {
                var tbd = table[i];
                tbd = tbd.Append(new List<string> { word }).ToList();
                foreach (var item in tbd)
                {
                    table[i + word.Length] = table[i + word.Length].Append(item).ToList();
                }  
            }
        }
        catch
        {

            
        }
            
    }
}
foreach (var item in table[target.Length])
{
    Console.WriteLine("__");
    foreach (var v in item)
    {
        Console.WriteLine(v + " ,");
    }
}

当前输出 #

__
purp ,
__
p ,
__
ur ,
__
p ,
__
le ,

预期输出 #

__
purp ,
le ,
__
p ,
ur ,
p ,
le ,

问题分析与修复 #

核心错误点 #

1. table[0]初始化错误：长度0的位置代表空字符串的拆分方式，应该初始化为包含一个空列表，这样才有基础组合可以追加单词。
2. 组合累积逻辑错误：原代码直接给table[i]追加单个单词的新列表，再把这些单个单词列表加到目标位置，没有基于已有组合进行扩展，导致每个结果都是单个单词。
3. 异常处理不当：用try-catch掩盖了越界问题，应该提前判断边界避免异常。

修复后的代码 #

List<string> wordbank = new List<string>() { "purp", "p", "ur", "le", "purpl" };
string target = "purple";
Dictionary<int, List<List<string>>> table = new();

// 初始化table，每个位置对应长度为i的子串的拆分组合
for (int i = 0; i < target.Length + 1; i++)
{
    table[i] = new List<List<string>>();
}

// 长度0的子串（空串）有一个拆分方式：空组合
table[0] = new List<List<string>> { new List<string>() };

for (int i = 0; i <= target.Length; i++)
{  
    // 如果当前位置没有拆分组合，直接跳过
    if (!table[i].Any()) continue;
    
    foreach (var word in wordbank)
    {
        // 检查当前位置加上单词长度是否超出目标字符串长度
        if (i + word.Length > target.Length) continue;
        
        // 检查子串是否匹配当前单词
        if (target.Substring(i, word.Length) == word)
        {
            // 遍历当前位置的所有已有组合，每个组合都追加当前单词，生成新组合
            foreach (var existingCombination in table[i])
            {
                var newCombination = new List<string>(existingCombination);
                newCombination.Add(word);
                // 将新组合添加到目标位置的列表中
                table[i + word.Length].Add(newCombination);
            }
        }
    }
}

// 输出结果
foreach (var item in table[target.Length])
{
    Console.WriteLine("__");
    foreach (var v in item)
    {
        Console.WriteLine(v + " ,");
    }
}

关键修改说明 #

• 修正table[0]的初始化，提供了组合扩展的基础。
• 遍历已有组合并生成新组合，确保每个新组合都是在原有组合的基础上追加当前单词，实现正确的组合累积。
• 替换try-catch为边界判断，代码更健壮且逻辑清晰。

修复后输出 #

__
purp ,
le ,
__
p ,
ur ,
p ,
le ,

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