最好的算法来找到dictonary

-2

字的字谜我得到的一个问题是这样的最好的算法来找到dictonary

我有一个List这是一个包含数百万字的字典，我给定输入一个字像OSPT onlt可形成2个字STOP和POST .. 我想找出在优化方式匹配在dictonary所有anagram字。

我解决了什么问题。

我给下面solution.I将取词和置换，并检查单词存在于字典或not.But这是N * N不optimized.Is有什么办法可以解决这个

来源

2013-12-19 chiru

@Bathsheba怎么会有帮助？ –

你每个字的字符的字母顺序排序，形成一个映射，其值是该关键词的列表项。

当你给一个字的找的字谜，你在这个词的字符字母顺序进行排序，并在地图上进行查找。

从你的例子并添加文字POOL，你会得到：

LOOP -> [LOOP, POOL, POLO] 
OPST -> [STOP, POST]

的Java代码会是这样的：

public class AnagramGenerator 
{ 
    private Map<String, Collection<String>> indexedDictionary; 

    public AnagramGenerator(List<String> dictionary) 
    { 
    this.indexedDictionary = index(dictionary); 
    } 

    public Collection<String> getAnagrams(String word) 
    { 
    return indexedDictionary.get(sort(word)); 
    } 


    private Map<String, Collection<String>> index(List<String> dictionary) 
    { 
    MultiMap<String, String> indexedDictionary = HashMultimap.create(); 

    for (String word : dictionary) 
    { 
     indexDictionary.put(sort(word), word); 
    } 

    return indexedDictionary.asMap(); 
    } 

    private String sort(String word) 
    { 
    List<Character> sortedCharacters= Arrays.asList(word.toCharArray()); 
    Collections.sort(sortedCharacters); 

    StringBuilder builder = new StringBuilder(); 
    for (Character character : sortedCharacters) 
    { 
     builder.append(character); 
    } 

    return builder.toString(); 
    } 
}

来源

2013-12-19 11:13:53

你可以做这个。

对每个单词进行排序并将其添加到已排序单词的MultiMap到实际单词中。
通过首先对单词排序来查找每个单词以用作anagram。

索引成本是O（N），其中N是词的数量。

之后排序的成本为O（M日志M）到M是字母数的字母排序。这与计算置换的成本相比非常便宜。

BTW这种方法，字只提前一次扫描。

来源

2013-12-19 11:13:10

这可以通过以下方式进行：

对于给定的话，保持它的所有字符的计数。例如对于OSTP，

count['O'] = 1; 
count['S'] = 1; 
count['T'] = 1; 
count['P'] = 1;

您可以像这样形成26个元素的数组。

然后同时通过字典迭代时，只检查其词具有相同的字符数。

来源

2013-12-19 11:13:27

您可能预处理列表：从更换任何字它与其排序的anagram（即abacaba变成aaaabbc）。该字符串唯一地表示任何字，它是字典中单词的字母组合。

然后，当你接收查询，排序在其信件和检查，如果这个词是在预处理字典。

来源

2013-12-19 11:14:11

为了获得最佳的速度，你可以映射字符到独特的首要价值，它们相乘（确保你有足够大量的），并使用该产品为用于存储合法的排列中的数字键。每个数字对于给定的一组置换是唯一的，因为这些字符形成了一个唯一的素数分解。

给定一个输入单词，重复该过程以获取该值，并直接访问该字典。与已排序字符串解决方案类似，但节省了排序开销并简化了关键比较。

参见这里在C相关的解决方案 - Generate same unique hash code for all anagrams

来源

2013-12-19 12:31:14 Leeor

最好的算法来找到dictonary

回答

相关问题