字符串组合与字符替换

Question

我正在尝试通过一个我以前没有见过的场景,并且正在努力想出一个算法来正确实现它.我的部分问题是对正确术语的朦胧回忆.我相信我需要的是标准"组合"问题的变体,但我很可能会离开那里.

场景 给定一个示例字符串"100"(让我们称之为x),生成x该交换的所有组合中的一个0(零)字符o(小写o).所以,对于简单的例子"100",我希望这个输出:

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

这将需要支持具有不同0字符数的不同长度的字符串,但假设永远不会有超过5个实例0.

我有这个非常简单的算法,适用于我的样本,"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");
}

我有一种唠叨的感觉,递归可能是我的朋友,但我正在努力弄清楚如何结合我需要的条件逻辑.

Answer 1

你的猜测是正确的; 递归是你挑战这个挑战的朋友.这是一个简单的解决方案:

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;                                    
}