字谜词分组算法

一尘不染

字谜词分组算法

algorithm

给定一组单词，我们需要找到字谜单词并使用最佳算法单独显示每个类别。

输入：

man car kile arc none like

输出：

man
car arc
kile like
none

我现在正在开发的最佳解决方案是基于哈希表，但是我正在考虑将字谜词转换为整数值的方程式。

示例：man =>’m’+’a’+’n’，但这不会给出唯一值。

有什么建议吗？

请参见C＃中的以下代码：

string line = Console.ReadLine();
string []words=line.Split(' ');
int[] numbers = GetUniqueInts(words);
for (int i = 0; i < words.Length; i++)
{
    if (table.ContainsKey(numbers[i]))
    {
        table[numbers[i]] = table[numbers[i]].Append(words[i]);
    }
    else
    {
        table.Add(numbers[i],new StringBuilder(words[i]));
    }

}

问题是如何开发GetUniqueInts(string [])方法。

阅读 242

2020-07-28

共1个答案

一尘不染

完全不用理会自定义哈希函数。在任何平台上都可以使用普通的字符串哈希函数。重要的是使哈希表的关键字具有“已排序单词”的概念-单词按字母排序，因此“ car”
=>“ acr”。所有字谜都有相同的“分类词”。

只需从“分类词”到“该分类词的词列表”中添加一个哈希即可。在LINQ中，这非常简单：

using System;
using System.Collections.Generic;
using System.Linq;

class FindAnagrams
{
    static void Main(string[] args)
    {
        var lookup = args.ToLookup(word => SortLetters(word));

        foreach (var entry in lookup)
        {
            foreach (var word in entry)
            {
                Console.Write(word);
                Console.Write(" ");
            }
            Console.WriteLine();
        }
    }

    static string SortLetters(string original)
    {
        char[] letters = original.ToCharArray();
        Array.Sort(letters);
        return new string(letters);
    }
}

样品使用：

c:\Users\Jon\Test>FindAnagrams.exe man car kile arc none like
man
car arc
kile like
none

2020-07-28