在语言的所有单词中搜索字词和变音符号

用字谜解决问题导致了这个想法:
如果从俄语词典中删除所有字谜和圣七字,还剩下多少个单词

词典包含各种形式的150万个单词,

您可以将每个单词进行比较,但是对于150万个条目,该单词又长又次优。
在一个无限内存的世界中,您可以生成每个单词的所有排列的子字符串并检查我们的字典,

但是有更好的解决方案吗?

让我们先从术语:

字谜-由字母重新排列获得的一个词
例:火箭马车

-一个可以由另一个词的字母词Sabanagram
例子: -这个词的sabanagram 火箭

任务

让我们说我们的字典由五个棘手的话:

火箭马车,,catsputum

前缀树(Trie)添加字典。树的
每个节点都包含一对:字母+单词中
的数字节点按字母顺序排列,并按单词



Algorithm 中的字母频率排序(以简化形式):

发言,n.r。cat:

我们正在寻找以单词的最小字母(“ k”)开头的节点

(在图中,这些节点以紫色标记)

。一旦找到这样的节点,我们就会在子树中查找包含所需数量的剩余字母的路径。

在节点K-1下方的单词痰中有一个O-2和T-1,这只猫足以满足我们

的要求,这种数据结构的优势在于,如果节点字母>而不是我们要

查看的字母,我们可以迅速退出子树。检查字典后,我们发现只有不是字谜或另一个词的讽刺

Java代码
 public boolean isAnagramOrSubAnagram(Word word) {
        Character minCharacter = word.getMinCharacter();

        Stack<TrieNode> stack = new Stack<>();
        stack.add(root);

        while (!stack.isEmpty()) {
            TrieNode node = stack.pop();

            for (Entry<TrieKey, TrieNode> entry : node.getChildren().entrySet()) {
                char character = entry.getKey().getCharacter();
                if (character < minCharacter) {
                    stack.add(entry.getValue());
                } else if (character > minCharacter) {
                    break;
                } else if (entry.getKey().getCount() >= word.getCharacterCount(minCharacter)) {
                    if (doesMinWordCharacterNodeContainAnagram(entry, word)) {
                        return true;
                    }
                }
            }
        }
        return false;
    }



完整的代码版本带有两个词典并进行测试

PS

对于150万个俄语词典,在13分钟内剩余242399个单词
对于45秒钟剩余41.6万个英语词典,在49秒内剩余

的单词如果下一个单词以它开头,则可以通过从中删除当前单词来优化原始词典

All Articles