Procure anagramas e sabanagramas em todas as palavras da língua

A resolução de problemas com anagramas levou à ideia:
Quantas palavras restam se você remover todos os anagramas e sangangrams do dicionário do idioma russo

O dicionário contém mais de 1,5 milhão de palavras em várias formas.Você

pode comparar cada palavra com cada uma, mas, para 1,5 milhão de entradas, é longa e não é ideal.
Em um mundo com memória infinita, você pode gerar substrings de todas as permutações de cada palavra e verificar nosso dicionário sobre elas,

mas existe uma solução melhor?

Vamos começar com a terminologia:

Anagrama - uma palavra obtida por rearranjo de letras
Exemplo: foguete e carruagem

Sabanagram - uma palavra que pode ser composta por letras de outra palavra
Exemplo: arch - sabanagrama da palavra foguete

Tarefa :

Digamos que nosso dicionário consiste em cinco palavras complicadas:

foguete , carruagem , arco , cat , sputum

Adicione um dicionário à árvore de prefixos (Trie)
Cada nó da árvore contém um par: letra + seu número na palavra
Os nós são classificados em ordem alfabética e pela frequência da letra na palavra



Algoritmo (de forma simplificada):

Tome a palavra, n.r. cat:

estamos procurando nós começando com a letra mínima da palavra ("k")

(na figura, esses nós são marcados em roxo).

Assim que encontramos esse nó, procuramos na subárvore o caminho que contém as letras restantes na quantidade necessária

Na palavra escarro abaixo do nó K-1, há O-2 e T-1, o que é suficiente para a nossa palavra cat.

A vantagem dessa estrutura de dados é que podemos sair rapidamente da subárvore se a letra do nó> do que a letra que estamos

vendo. Depois de verificar nosso dicionário, descobrimos que apenas escarro não é um anagrama ou sabanagrama de outra palavra

Código 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;
    }



→ A versão completa do código com dois dicionários e testes

PS

Para um dicionário russo de 1,5 milhão, 242399 palavras restantes em 13 minutos
Para um dicionário inglês de 416 mil restantes 49251 em 45 segundos

Você pode otimizar o dicionário original removendo a palavra atual, se a próxima começar com ele

All Articles