Dada una cadena, se encuentran todas sus permutaciones que son una palabra en el diccionario de

Esta es una pregunta de la entrevista:Dada una cadena, se encuentran todas sus permutaciones que son una palabra en el diccionario de

Dada una cadena, encontrar todas sus permutaciones que son una palabra en el diccionario.

Mi solución:

Ponga todas las palabras del diccionario en un árbol de sufijos y después buscar cada permutación de la cadena en el árbol. El tiempo de búsqueda es O(n), donde n es el tamaño de la cadena. Pero la cadena puede tener permutaciones n!.

¿Cómo puedo mejorar la eficiencia?

Fuente

2011-12-08 user1002288

El nombre usual para esta tarea es encontrar anagramas, hay un enfoque clásico que usted debería ser capaz de encontrar con ese término de búsqueda. – Per

Su enfoque general no está nada mal.

Sin embargo, puede evitar tener que buscar cada permutación reorganizando su palabra para que todos sus caracteres estén en orden alfabético, luego buscar en un diccionario donde cada palabra se reorganice de manera similar en orden alfabético y se mapee al original palabra.

Me doy cuenta de que puede ser un poco difícil de entender como es, así que aquí hay un ejemplo. Diga que su palabra es salto. Reorganizar esto a aelp.

Ahora en su diccionario puede tener las palabras alegato y pálido. Después de haber hecho como se sugiere, su diccionario voluntad (entre otras cosas) contienen las siguientes asignaciones:

... 
aelp -> pale 
aelp -> plea 
...

Así que ahora, para encontrar sus anagramas sólo tiene que encontrar entradas para AELP (utilizando, por ejemplo, un suffix- enfoque de árbol como se sugiere), en lugar de los 4! = 24 permutaciones de salto.

Fuente

2011-12-08 04:46:12 Mac

este es mi análisis para tu idea. Clasifica cada palabra en el diccionario. O (n * m * lg m), n es el tamaño del diccionario, m es la longitud promedio de la palabra Ponga cada par en un hashmap >. Si la clave es un conflicto, coloque la palabra sin clasificar en una lista . Esto en). Ordene la cadena dada, O (p lg p), p es el tamaño de la cadena. Busque la cadena ordenada (un anagrama) en el hashmap. O (1). La lista de la clave del anagrama es todas las permutaciones. Entonces, totalmente es O (n * m * lg m + p lg p), por lo general, p << n, entonces tenemos O (n * m * lg m) y espacio O (n). – user1002288

Una solución alternativa rápida: todo depende del tamaño de las estructuras de datos en cuestión.

Si el diccionario es razonablemente pequeño y la cadena es razonablemente larga, puede repasar cada entrada en el diccionario y determinar si se trata de una permutación de la cadena. Puede ser más inteligente: puede ordenar el diccionario y omitir ciertas entradas.

Fuente

2011-12-08 04:38:36

Puede construir un mapa de una lista ordenada de caracteres a una lista de palabras.

Por ejemplo, teniendo en cuenta los siguientes:

Array (him, hip, his, hit, hob, hoc, hod, hoe, hog, hon, hop, hos, hot)

le ordenarlos internamente:

Array (him, hip, his, hit, bho, cho, dho, eho, gho, hno, hop, hos, hot)

tipo del resultado:

Array (bho, cho, dho, eho, gho, him, hip, his, hit, hno, hop, hos, hot)

En esta pequeña muestra, no lo hacemos tener una coincidencia, pero para una palabra en particular, la ordenarías internamente, y con esto como una mirada clave en tu mapa.

Fuente

2011-12-08 04:49:21

¿Por qué no utiliza un mapa hash para almacenar las palabras del diccionario? Entonces obtienes O (1) tiempo de búsqueda. Y si su entrada es en inglés, puede construir otra tabla para contar todas las letras posibles en su diccionario, usando esta tabla, puede filtrar algunas entradas al principio. Lo que sigue es un ejemplo:

result_list = empty; 

for(char in input) 
{ 
    if(char not in letter_table) 
    { 
     return result_list; 
    } 
} 

for(entry in permutations of input) 
{ 
    if(entry in dictionary_hash_table) 
    { 
     result_list->add_entry(); 
    } 
} 

return result_list

Fuente

2011-12-08 05:07:18 Shawnone

Otra solución simple podría ser tan algoritmo continuación,

1) Use "next_permutation" para encontrar una permutación única.

2) Use "find/find_if" para buscarlo en un diccionario.

Fuente

2011-12-08 06:48:27 rakesh

Debe poner las palabras en un trie. Luego puede buscar la palabra a medida que genera las permutaciones. Puede omitir bloques enteros de permutaciones con la primera parte que no está en el trie.

http://en.wikipedia.org/wiki/Trie

Fuente

2011-12-08 17:37:32 Fantius

Dada una cadena, se encuentran todas sus permutaciones que son una palabra en el diccionario de

Respuesta

Cuestiones relacionadas