非常简单的字谜求解器

• 下载源代码 - 2.45 KB

引言

我回来了！这是我五年来的第一篇帖子！如果你之前参加过微软的面试，你可能遇到过这类递归问题。我已经写了几种不同的解决方案，这是目前为止最新也是最小的一个。

背景

适当地锻炼一下思维总是好的。如果你正在为工作进行技术评估，希望它能帮助你，祝你好运！

Using the Code

如果你有 VS2010，你就会知道如何运行这个项目。这是递归方法

static void GenerateAnagram(IList<string> result, string prefix, string src)
{
    if (src.Length == 0)
    {
        result.Add(prefix);
        return;
    }

    for (int i = 0; i < src.Length; i++ )
    {
        string tempPrefix = src[i].ToString();
        string newSrc = src.Substring(0, i) + src.Substring(i + 1);
        var temp = new List<string>();
        GenerateAnagram(temp, tempPrefix, newSrc);
        foreach (var s in temp)
        {
            result.Add(prefix + s);
        }
    }
}

这是调用它的方法

var result = new List<string>();
GenerateAnagram(result, "", "ABC");

在一位读者指出内存问题后，这里是另一种使用递归的方法

static IEnumerable<string> GenerateAnagramAlt(string src)
{
    if (src.Length == 0) yield break;
    if (src.Length == 1) yield return src;

    foreach (string rest in GenerateAnagramAlt(src.Substring(1)))
    {
        for (int i = 0; i < src.Length; i++)
        {
            string temp = rest.Substring(0, i) + src[0] + rest.Substring(i);
            yield return temp;
        }
    }
}

我更喜欢这个方法，因为它没有内存限制，并且当 n >= 9 个字符时，速度几乎快一倍。我也喜欢它的 IEnumberable 语法！我已经更新了一个新项目来包含源代码文件。感谢我的朋友 ajasin1，他提出了这个想法。

关注点

我没有包含过滤重复案例的逻辑，因为可以使用 LINQ 很容易地完成。

历史

• 2011-09-08：首次发布。
• 2011-09-09：发布 2.0 版本，用于 GenerateAnagramAlt。