Busque anagramas y sabanagramas en todas las palabras del idioma.

Resolver problemas con anagramas llevó a pensar:
¿Cuántas palabras quedan si elimina todos los anagramas y sangangramas del diccionario del idioma ruso?

El diccionario contiene más de 1.5 millones de palabras en varias formas.

Puede comparar cada palabra con cada una, pero para 1.5 millones de entradas es largo y no es óptimo.
En un mundo con memoria infinita, puede generar subcadenas de todas las permutaciones de cada palabra y consultar nuestro diccionario,

pero ¿hay alguna solución mejor?

Comencemos con la terminología:

anagrama - una palabra obtenida por reordenamiento de letras
Ejemplo: cohete y carro

Sabanagram - una palabra que puede estar compuesta de letras de otra palabra
Ejemplo: arco - sabanagrama de la palabra cohete

Tarea :

Digamos que nuestro diccionario consta de cinco palabras difíciles:

cohete , carro , arco , cat , sputum

Agregue un diccionario al árbol de prefijos (Trie)
Cada nodo de árbol contiene un par: letra + su número en la palabra
Los nodos se ordenan alfabéticamente y por la frecuencia de la letra en la palabra



Algoritmo (en forma simplificada):

Toma la palabra, n.r. cat:

Estamos buscando nodos que comiencen con la letra mínima de la palabra ("k")

(en la figura, dichos nodos están marcados en púrpura)

Tan pronto como encontramos dicho nodo, buscamos en el subárbol la ruta que contiene las letras restantes en la cantidad requerida

En la palabra esputo debajo del nodo K-1 hay O-2 y T-1, que es suficiente para nuestra palabra cat.

La ventaja de dicha estructura de datos es que podemos salir rápidamente del subárbol si la letra del nodo> que la letra que estamos

viendo. Después de revisar nuestro diccionario, descubrimos que solo el esputo no es un anagrama o sabanagram de otra palabra

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;
    }



→ La versión completa del código con dos diccionarios y pruebas

PS

Para un diccionario ruso de 1.5 millones, 242399 palabras restantes en 13 minutos
Para un diccionario de inglés de 416 mil restantes 49251 en 45 segundos

Puede optimizar el diccionario original eliminando la palabra actual si el siguiente comienza con él

All Articles