c# - 带字符替换的字符串组合

Question

我正在尝试处理一个我以前从未见过的场景，并且正在努力想出一种算法来正确地实现它。我的部分问题是对正确术语的模糊记忆。我相信我需要的是标准“组合”问题的变体，但我很可能会离开那里。

场景给定一个示例字符串 "100"(我们称它为 x)，生成 x 的所有组合，换出其中一个 0 (零)个字符表示 o(小写 o)。因此，对于 "100" 的简单示例，我希望得到以下输出:

• “100”
• “10o”
• "1o0"
• “1oo”

这需要支持具有不同数量的 0 字符的可变长度字符串，但假设 0 的实例永远不会超过 5 个。

我有一个非常简单的算法，它适用于我的 "100" 示例，但对于任何更长/更复杂的东西都会崩溃:

public IEnumerable<string> Combinations(string input)
{
    char[] buffer = new char[input.Length];

    for(int i = 0; i != buffer.Length; ++i)
    {
        buffer[i] = input[i];
    }

    //return the original input
    yield return new string(buffer);

    //look for 0's and replace them
    for(int i = 0; i != buffer.Length; ++i)
    {
        if (input[i] == '0')
        {
            buffer[i] = 'o';
            yield return new string(buffer);
            buffer[i] = '0';
        }
    }

    //handle the replace-all scenario
    yield return input.Replace("0", "o");
}

我有一种挥之不去的感觉递归可能是我的 friend ，但我正在努力弄清楚如何在这里合并我需要的条件逻辑。

Answer 1

您的猜测是正确的；递归是你应对这一挑战的好 helper 。这是一个简单的解决方案:

public static IEnumerable<string> Combinations(string input)
{
    int firstZero = input.IndexOf('0');   // Get index of first '0'
    if (firstZero == -1)      // Base case: no further combinations
        return new string[] { input };

    string prefix = input.Substring(0, firstZero);    // Substring preceding '0'
    string suffix = input.Substring(firstZero + 1);   // Substring succeeding '0'
    // e.g. Suppose input was "fr0d00"
    //      Prefix is "fr"; suffix is "d00"

    // Recursion: Generate all combinations of suffix
    // e.g. "d00", "d0o", "do0", "doo"
    var recursiveCombinations = Combinations(suffix);

    // Return sequence in which each string is a concatenation of the
    // prefix, either '0' or 'o', and one of the recursively-found suffixes
    return 
        from chr in "0o"  // char sequence equivalent to: new [] { '0', 'o' }
        from recSuffix in recursiveCombinations
        select prefix + chr + recSuffix;                                    
}