对字谜词进行分组的算法

Question

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

输入:

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 [])方法。

Answer 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