47

如果其中一个词与另一个词的字符完全相同，则两个词是字谜。

示例：Anagram&Nagaram是字谜（不区分大小写）。

现在有很多类似的问题。找出两个字符串是否是字谜的几种方法是：

1） Sort字符串并比较它们。

2）为这些字符串创建一个frequency map并检查它们是否相同。

但是在这种情况下，我们给出了一个单词（为了简单起见，我们假设只有一个单词，并且它只有一个单词字谜），我们需要为此找到字谜。

我想到的解决方案是，我们可以生成单词的所有排列并检查字典中存在哪些单词 。但显然，这是非常低效的。是的，词典也有。

那么我们有什么选择呢？

我还在一个类似的线程中读到，可以使用某些东西来完成，Tries但该人没有解释算法是什么以及我们为什么首先使用 Trie，只是在 Python 或 Ruby 中也提供了一个实现。所以这并没有真正的帮助，这就是我创建这个新线程的原因。如果有人想分享他们的实现（C、C++ 或 Java 除外），也请解释一下。

4

13 回答 13

76

示例算法：

Open dictionary
Create empty hashmap H
For each word in dictionary:
  Create a key that is the word's letters sorted alphabetically (and forced to one case)
  Add the word to the list of words accessed by the hash key in H

要检查给定单词的所有字谜：

Create a key that is the letters of the word, sorted (and forced to one case)
Look up that key in H
You now have a list of all anagrams

构建速度相对较快，查找速度极快。

于 2012-09-18T13:25:12.557 回答
19

我想出了一个新的解决方案。它使用算术基本定理。所以这个想法是使用前 26 个素数的数组。然后对于输入单词中的每个字母，我们得到相应的素数 A = 2、B = 3、C = 5、D = 7 ……然后我们计算输入单词的乘积。接下来，我们对字典中的每个单词执行此操作，如果一个单词与我们的输入单词匹配，那么我们将其添加到结果列表中。所有字谜将具有相同的签名，因为

任何大于 1 的整数要么是素数，要么可以写成素数的唯一乘积（忽略顺序）。

这是代码。我将单词转换为大写，65 是 A 的位置，对应于我的第一个素数：

private int[] PRIMES = new int[] { 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31,
        37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103,
        107, 109, 113 };

这是方法：

 private long calculateProduct(char[] letters) {
    long result = 1L;
    for (char c : letters) {
        if (c < 65) {
            return -1;
        }
        int pos = c - 65;
        result *= PRIMES[pos];
    }
    return result;
}
于 2015-03-09T18:13:32.763 回答
2

我们知道，如果两个词的长度不同，它们就不是字谜。因此，您可以将字典划分为相同长度的单词组。

现在我们只关注其中一个组，基本上所有单词在这个较小的宇宙中都具有完全相同的长度。

如果每个字母位置都是一个维度，并且该维度中的值基于字母（比如 ASCII 码）。然后就可以计算词向量的长度了。

例如，说'A'=65，'B'=66，然后length("AB") = sqrt(65*65 + 66*66)。显然，length("AB") = length("BA")。

显然，如果两个词是字谜，那么它们的向量具有相同的长度。下一个问题是，如果两个单词（具有相同数量的字母）向量具有相同的长度，它们是字谜吗？直觉上，我会说不，因为所有具有该长度的向量都形成一个球体，所以有很多。不确定，因为在这种情况下我们在整数空间中，实际上有多少。

但至少它允许您进一步划分您的字典。对于字典中的每个单词，计算向量的距离： for(each letter c) { distance += c*c }; distance = sqrt(distance);

然后为所有长度的单词创建一个映射n，并用距离作为键，值是n产生特定距离的长度单词列表。

您将为每个距离创建一张地图。

然后您的查找变成以下算法：

  1. 根据单词的长度使用正确的字典图
  2. 计算单词向量的长度
  3. 查找与该长度匹配的单词列表
  4. 浏览列表并使用朴素算法挑选字谜现在候选列表大大减少
于 2012-09-18T13:20:42.550 回答
2
  • 将单词减少为 - 说 - 小写 ( clojure.string/lower-case)。
  • group-by按字母频率图 ( ) 对它们进行分类( frequencies)。
  • 删除频率图，
  • ...离开字谜的集合。

( These) 是 Lisp 方言 Clojure 中的对应函数。

整个函数可以这样表示：

(defn anagrams [dict]
  (->> dict
       (map clojure.string/lower-case)
       (group-by frequencies)
       vals))

例如，

(anagrams ["Salt" "last" "one" "eon" "plod"])
;(["salt" "last"] ["one" "eon"] ["plod"])

将每个事物映射到其集合的索引函数是

(defn index [xss]
  (into {} (for [xs xss, x xs] [x xs])))

因此，例如，

((comp index anagrams) ["Salt" "last" "one" "eon" "plod"])
;{"salt" ["salt" "last"], "last" ["salt" "last"], "one" ["one" "eon"], "eon" ["one" "eon"], "plod" ["plod"]}

...comp函数组合运算符在哪里。

于 2017-04-27T11:07:22.593 回答
1

Well Tries 可以更容易地检查单词是否存在。因此，如果您将整个字典放在一个 trie 中：

http://en.wikipedia.org/wiki/Trie

然后你可以相信你的话并通过获取一个字符并递归地检查我们是否可以通过其余字符的任何组合（一次添加一个字符）沿着Trie“走”来进行简单的回溯。当递归分支中使用了所有字符并且 Trie 中存在有效路径时，则该单词存在。

Trie 有帮助，因为它是一个很好的停止条件：我们可以检查字符串的一部分，例如“Anag”是否是 trie 中的有效路径，如果不是，我们可以打破那个特定的递归分支。这意味着我们不必检查字符的每一个排列。

在伪代码中

checkAllChars(currentPositionInTrie, currentlyUsedChars, restOfWord)
    if (restOfWord == 0)
    {
         AddWord(currentlyUsedChar)
    }
    else 
    {
        foreach (char in restOfWord)
        {
            nextPositionInTrie = Trie.Walk(currentPositionInTrie, char)
            if (nextPositionInTrie != Positions.NOT_POSSIBLE)
            {
                checkAllChars(nextPositionInTrie, currentlyUsedChars.With(char), restOfWord.Without(char))
            }
        }   
    }

显然，您需要一个不错的 Trie 数据结构，它允许您逐步“走”下树并检查每个节点是否存在具有给定字符的路径到任何下一个节点......

于 2012-09-18T13:04:57.453 回答
1 
static void Main(string[] args)
{

    string str1 = "Tom Marvolo Riddle";
    string str2 = "I am Lord Voldemort";

    str2=  str2.Replace(" ", string.Empty);
    str1 = str1.Replace(" ", string.Empty);
    if (str1.Length != str2.Length)
        Console.WriteLine("Strings are not anagram");
    else
    {
        str1 = str1.ToUpper();
        str2 = str2.ToUpper();
        int countStr1 = 0;
        int countStr2 = 0;
        for (int i = 0; i < str1.Length; i++)
        {
            countStr1 += str1[i];
            countStr2 += str2[i];

        }
        if(countStr2!=countStr1)
            Console.WriteLine("Strings are not anagram");
        else Console.WriteLine("Strings are  anagram");

    }
    Console.Read();
}
于 2015-05-27T13:00:47.940 回答
0

生成所有排列很容易，我猜你担心在字典中检查它们的存在是“非常低效”的部分。但这实际上取决于您用于字典的数据结构：当然，单词列表对于您的用例来说效率低下。说到Tries，它们可能是一个理想的表示，而且也非常有效。

另一种可能性是对您的字典进行一些预处理，例如构建一个哈希表，其中键是单词的字母排序，值是单词列表。您甚至可以序列化此哈希表，以便将其写入文件并稍后快速重新加载。然后查找字谜，您只需对给定的单词进行排序并在哈希表中查找相应的条目。

于 2012-09-18T13:05:21.137 回答
0

这取决于您如何存储字典。如果它是一个简单的单词数组，那么没有算法会比线性更快。

如果它已排序，那么这是一种可能有效的方法。我刚刚发明了它，但我猜它比线性方法更快。

  1. 将您的字典表示为 D，当前前缀为 S。S = 0；
  2. 您为您的单词创建频率图。让我们用 F 来表示它。
  3. 使用二进制搜索查找指向字典中每个字母开头的指针。让我们用 P 来表示这个指针数组。
  4. 对于从 A 到 Z 的每个字符 c，如果 F[c] == 0，则跳过它，否则
    • S += c;
    • F[c] --;
    • P <- 对于每个字符 i P[i] = 指向以 S+i 开头的第一个单词的指针。
    • 递归调用第 4 步，直到找到与您的单词匹配或直到您发现不存在这样的匹配。

无论如何，我会这样做。应该有一种更传统的方法，但这比线性方法更快。

于 2012-09-18T13:17:13.927 回答
0

试图实现 hashmap 解决方案

public class Dictionary {

    public static void main(String[] args){

    String[] Dictionary=new String[]{"dog","god","tool","loot","rose","sore"};

    HashMap<String,String> h=new HashMap<String, String>();

    QuickSort q=new QuickSort();

    for(int i=0;i<Dictionary.length;i++){

        String temp =new String();

        temp= q.quickSort(Dictionary[i]);//sorted word e.g dgo for dog

        if(!h.containsKey(temp)){
           h.put(temp,Dictionary[i]);
        }

        else
        {
           String s=h.get(temp);
           h.put(temp,s + " , "+ Dictionary[i]);
        }
    }

    String word=new String(){"tolo"};

    String sortedword = q.quickSort(word);

    if(h.containsKey(sortedword.toLowerCase())){ //used lowercase to make the words case sensitive

        System.out.println("anagrams from Dictionary   :  " + h.get(sortedword.toLowerCase()));
    }

}
于 2013-12-22T20:57:22.710 回答
0
  • 计算字典中每个单词的频率计数向量，一个字母列表长度的向量。
  • 生成字母列表长度的随机高斯向量

  • 在这个随机方向上投影每个字典单词的计数向量并存储值（插入以便对值数组进行排序）。

  • 给定一个新的测试词，将其投射到与字典词相同的随机方向上。

  • 执行二进制搜索以查找映射到相同值的单词列表。
  • 验证如上获得的每个单词是否确实是一个真正的字谜。如果没有，请将其从列表中删除。
  • 返回列表的剩余元素。

PS：上述过程是质数过程的概括，可能会导致大数（以及因此计算精度问题）

于 2016-03-08T06:21:24.417 回答
0 
# list of words
words = ["ROOPA","TABU","OOPAR","BUTA","BUAT" , "PAROO","Soudipta",
        "Kheyali Park", "Tollygaunge", "AROOP","Love","AOORP",
         "Protijayi","Paikpara","dipSouta","Shyambazaar",
        "jayiProti", "North Calcutta", "Sovabazaar"]

#Method 1
A = [''.join(sorted(word)) for word in words]

dict ={}

for indexofsamewords,samewords in enumerate(A):
    dict.setdefault(samewords, []).append(indexofsamewords)
    
print(dict)
#{'AOOPR': [0, 2, 5, 9, 11], 'ABTU': [1, 3, 4], 'Sadioptu': [6, 14], ' KPaaehiklry': [7], 'Taeggllnouy': [8], 'Leov': [10], 'Paiijorty': [12, 16], 'Paaaikpr': [13], 'Saaaabhmryz': [15], ' CNaachlortttu': [17], 'Saaaaborvz': [18]}

for index in dict.values(): 
    print( [words[i] for i in index ] )

输出 ：

['ROOPA', 'OOPAR', 'PAROO', 'AROOP', 'AOORP']
['TABU', 'BUTA', 'BUAT']
['Soudipta', 'dipSouta']
['Kheyali Park']
['Tollygaunge']
['Love']
['Protijayi', 'jayiProti']
['Paikpara']
['Shyambazaar']
['North Calcutta']
['Sovabazaar']
于 2021-01-12T07:10:01.773 回答
-3

一种解决方案是 - 将素数映射到字母字符并乘以素数

For ex - 

    a -> 2
    b -> 3
    ......
    .......
    ......
    z -> 101

所以

'ab' -> 6
'ba' -> 6
'bab' -> 18
'abba' -> 36
'baba' -> 36

获取给定单词的 MUL_number。返回字典中与给定单词具有相同 MUL_number 的所有单词

于 2015-07-16T18:39:09.093 回答
-3

首先检查字符串的长度是否相同。然后检查两个字符串中字符的总和是否相同（即ascii代码总和）然后这些单词是字谜，否则不是字谜

于 2016-09-28T17:18:50.300 回答