查找输入的字符串集字谜..？ [英] Find anagram of input on set of strings..?

问题描述

给定一组字符串（大套），并输入字符串，则需要有效地找到输入字符串的所有字谜。你会使用什么数据结构。并使用，你将如何找到字谜？

Given a set of strings (large set), and an input string, you need to find all the anagrams of the input string efficiently. What data structure will you use. And using that, how will you find the anagrams?

这是我想到的事情是这些：

Things that I have thought of are these:

1. 使用地图

一）消除所有的单词，比输入的增加/减少字母。

a) eliminate all words with more/less letters than the input.

b）将输入的字符映射

b) put the input characters in map

C）遍历地图的每个字符串，看看是否所有的字母都present他们的计数。

c) Traverse the map for each string and see if all letters are present with their count.

使用尝试次数

a）将具有字符权数转换为线索的所有字符串。

a) Put all strings which have the right number of characters into a trie.

二）遍历每个分支，并走向深入，如果这封信是包含在输入。

b) traverse each branch and go deeper if the letter is contained in the input.

c）若叶达成的字是一个字谜

c) if leaf reached the word is an anagram

任何人都可以找到一个更好的解决方案？

Can anyone find a better solution?

是否有你在上面的方法发现什么问题？

Are there any problems that you find in the above approaches?

推荐答案

建立一个频率地图的每一个字，并比较这些地图。

Build a frequency-map from each word and compare these maps.

伪code：

class Word

  string word
  map<char, int> frequency

  Word(string w)
    word = w
    for char in word
      int count = frequency.get(char)
      if count == null
        count = 0
      count++
      frequency.put(char, count)

  boolean is_anagram_of(that)
    return this.frequency == that.frequency 

这篇关于查找输入的字符串集字谜..？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！