19

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

输入：

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

4

14 回答 14

39

根本不用担心自定义哈希函数。在您的平台上使用普通的字符串散列函数。重要的是让哈希表的键成为“排序词”的概念 - 单词按字母排序，因此“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
于 2008-12-28T09:38:04.190 回答
19

我使用了一个受哥德尔启发的方案：

将素数 P_1 到 P_26 分配给字母（以任何顺序，但要获得较小的散列值最好给普通字母小素数）。

建立单词中字母的直方图。

然后哈希值是每个字母的相关素数乘以它的频率的幂。这为每个字谜赋予了独特的价值。

Python代码：

primes = [2, 41, 37, 47, 3, 67, 71, 23, 5, 101, 61, 17, 19, 13, 31, 43, 97, 29, 11, 7, 73, 83, 79, 89, 59, 53]


def get_frequency_map(word):
    map = {}

    for letter in word:
        map[letter] = map.get(letter, 0) + 1

    return map


def hash(word):
    map = get_frequency_map(word)
    product = 1
    for letter in map.iterkeys():
        product = product * primes[ord(letter)-97] ** map.get(letter, 0)
    return product

这巧妙地将寻找子字谜的棘手问题转化为分解大数的（也称为棘手的）问题......

于 2008-12-28T11:05:58.147 回答
7

用于咯咯笑的 Python 版本：

from collections import defaultdict
res = defaultdict(list)
L = "car, acr, bat, tab, get, cat".split(", ")

for w in L:
    res["".join(sorted(w))].append(w)

print(res.values())
于 2008-12-28T10:04:43.980 回答
3

我认为您不会找到比具有自定义散列函数的散列表更好的东西（在散列之前对单词的字母进行排序）。

字母的总和永远不会起作用，因为你不能真正使'ac'和'bb'不同。

于 2008-12-28T09:16:01.347 回答
3

您将需要大整数（或实际上是位向量），但以下可能有效

每个字母的第一次出现被分配该字母的位数，第二次出现获得该字母的位数+ 26。

例如

a #1 = 1 b #1 = 2 c #1 = 4 a #2 = 2^26 b #2 = 2 ^ 27

然后，您可以将这些加在一起，以根据单词的字母获得唯一的值。

您对单词值的存储要求将是：

n * 26 位

其中 n 是任何重复字母的最大出现次数。

于 2008-12-28T09:35:09.623 回答
2

我不会使用散列，因为它增加了查找和添加的额外复杂性。散列、排序和乘法都将比具有跟踪唯一性的简单的基于数组的直方图解决方案慢。最坏的情况是 O(2n)：

// structured for clarity
static bool isAnagram(String s1, String s2)
{
    int[] histogram = new int[256];

    int uniques = 0;

    // scan first string
    foreach (int c in s1)
    {
        // count occurrence
        int count = ++histogram[c];

        // count uniques
        if (count == 1)
        {
            ++uniques;
        }
    }

    // scan second string
    foreach (int c in s2)
    {
        // reverse count occurrence
        int count = --histogram[c];

        // reverse count uniques
        if (count == 0)
        {
            --uniques;
        }
        else if (count < 0) // trivial reject of longer strings or more occurrences
        {
            return false;
        }
    }

    // final histogram unique count should be 0
    return (uniques == 0);
}
于 2011-04-13T02:23:28.303 回答
1

我之前用一个简单的字母计数数组实现了这一点，例如：

unsigned char letter_frequency[26];

然后将其与每个单词一起存储在数据库表中。具有相同字母频率“签名”的单词是字谜，一个简单的 SQL 查询然后直接返回一个单词的所有字谜。

通过对一个非常大的字典进行一些实验，我发现没有任何单词超过任何字母的频率计数 9，因此“签名”可以表示为一串数字 0..9（通过打包可以很容易地将大小减半转换成十六进制的字节，并通过二进制编码进一步减少数字，但到目前为止我没有为此烦恼）。

这是一个 ruby​​ 函数，用于计算给定单词的签名并将其存储到哈希中，同时丢弃重复项。我后来从哈希中构建了一个 SQL 表：

def processword(word, downcase)
  word.chomp!
  word.squeeze!(" ") 
  word.chomp!(" ")
  if (downcase)
    word.downcase!
  end
  if ($dict[word]==nil) 
    stdword=word.downcase
    signature=$letters.collect {|letter| stdword.count(letter)}
    signature.each do |cnt|
      if (cnt>9)
        puts "Signature overflow:#{word}|#{signature}|#{cnt}"
      end
    end
    $dict[word]=[$wordid,signature]
    $wordid=$wordid+1
  end
end
于 2008-12-28T10:06:45.380 回答
1

为字母 az 分配一个唯一的素数

迭代您的单词数组，根据每个单词中的字母创建质数乘积。
将该产品与相应的单词一起存储在您的单词列表中。

对数组进行排序，按产品升序。

迭代数组，在每次产品更改时进行控制中断。

于 2008-12-28T21:45:34.720 回答
0

在 C 中，我刚刚实现了以下散列，它基本上对字典中的单词是否包含特定字母进行 26 位位掩码。因此，所有字谜都具有相同的哈希值。哈希不考虑重复的字母，所以会有一些额外的重载，但它仍然比我的 perl 实现更快。

#define BUCKETS 49999

struct bucket {
    char *word;
    struct bucket *next;
};

static struct bucket hash_table[BUCKETS];

static unsigned int hash_word(char *word)
{
    char *p = word;
    unsigned int hash = 0;

    while (*p) {
        if (*p < 97 || *p > 122) {
            return 0;
        }
        hash |= 2 << (*p - 97);
        *p++;
    }

    return hash % BUCKETS;
}

重载的桶创建并添加为链表等。然后只需编写一个函数，确保与哈希值匹配的单词长度相同，并且每个单词中的字母是 1 到 1 并将其作为匹配返回。

于 2009-08-12T14:29:26.863 回答
0

我将根据示例单词和其他我不关心的字母生成 hasmap。

例如，如果单词是“汽车”，我的哈希表将是这样的： a,0 b,MAX c,1 d,MAX e,MAX ... .. r,2 。因此，任何大于 3 的都将视为不匹配

（更多调整...）我的比较方法将比较哈希计算本身中的哈希总数。一旦它可以识别出单词不相等，它就不会继续。

public static HashMap<String, Integer> getHashMap(String word) {
        HashMap<String, Integer> map = new HashMap<String, Integer>();
        String[] chars = word.split("");
        int index = 0;
        for (String c : chars) {
            map.put(c, index);
            index++;
        }
        return map;
    }

    public static int alphaHash(String word, int base,
            HashMap<String, Integer> map) {
        String[] chars = word.split("");
        int result = 0;
        for (String c : chars) {
            if (c.length() <= 0 || c.equals(null)) {
                continue;
            }
            int index = 0;
            if (map.containsKey(c)) {
                index = map.get(c);
            } else {
                index = Integer.MAX_VALUE;
            }
            result += index;
            if (result > base) {
                return result;
            }
        }
        return result;
    }

主要方法

  HashMap<String, Integer> map = getHashMap(sample);
        int sampleHash = alphaHash(sample, Integer.MAX_VALUE, map);
        for (String s : args) {
                if (sampleHash == alphaHash(s, sampleHash, map)) {
                    System.out.print(s + " ");
                }
            }
于 2010-03-19T23:23:05.187 回答
0

字谜可以通过以下方式找到：

  1. 单词的长度应该匹配。
  2. 根据整数值执行每个字符的加法。如果您对 anagram 执行相同的操作，此总和将匹配。
  3. 根据整数值执行每个字符的乘法。如果您对 anagram 执行相同的操作，则评估值将匹配。

所以我想通过以上三个验证，我们可以找到字谜。如我错了请纠正我。

示例：abc cba

两个单词的长度都是 3。

两个单词的单个字符之和为 294。

这两个词的单个字符的产品是 941094。

于 2012-02-27T17:23:10.320 回答
0

除了其他有用的答案之外，只想添加简单的 python 解决方案：

def check_permutation_group(word_list):
    result = {}

    for word in word_list:
        hash_arr_for_word = [0] * 128  # assuming standard ascii

        for char in word:
            char_int = ord(char)
            hash_arr_for_word[char_int] += 1

        hash_for_word = ''.join(str(item) for item in hash_arr_for_word)

        if not result.get(hash_for_word, None):
            result[str(hash_for_word)] = [word]
        else:
            result[str(hash_for_word)] += [word]

return list(result.values())
于 2018-01-03T11:47:51.957 回答
0

蟒蛇代码：

line = "man car kile arc none like"
hmap = {}
for w in line.split():
  ws = ''.join(sorted(w))
  try:
    hmap[ws].append(w)
  except KeyError:
    hmap[ws] = [w]

for i in hmap:
   print hmap[i]

输出：

['car', 'arc']
['kile', 'like']
['none']
['man']
于 2018-02-21T04:32:30.453 回答
-1

JavaScript 版本。使用散列。

时间复杂度： 0(nm) ，其中 n 是字数，m 是字长

var words = 'cat act mac tac ten cam net'.split(' '),
    hashMap = {};

words.forEach(function(w){
    w = w.split('').sort().join('');
    hashMap[w] = (hashMap[w]|0) + 1;
});

function print(obj,key){ 
    console.log(key, obj[key]);
}

Object.keys(hashMap).forEach(print.bind(null,hashMap))
于 2013-09-02T22:09:19.440 回答