¿Cómo puedo encontrar las palabras en la matriz de letras

Question

Esta es otra pregunta que me hicieron en la entrevista telefónica:

Dado un diccionario y un crucigrama (matriz 2d de caracteres) encontrar todas las palabras del diccionario que se pueden encontrar en el crucigrama.

En lo único que podía pensar era en hash el diccionario, encontrar todas las palabras posibles en el crucigrama y buscar en el hash. No pude optimizarlo todo.

hay que admitir preguntas de la entrevista de Microsoft son difíciles :(

Por favor, dame las líneas para pensar en

Answer 1

¿Qué tal:.

• construir un árbol de búsqueda para el diccionario (un nivel por carta)
• para cada posición en la cuadrícula, comience a buscar a través del índice, un carácter a la vez, y proceda en cada dirección permitida hasta que no queden entradas en el índice, o llegue a un límite de la cuadrícula

No creo que un hash sea una optimización muy útil aquí.

Answer 2

Supongamos que el diccionario contiene n palabras de longitud media k, y la matriz contiene m ² caracteres.

1. Preprocesar el diccionario en un prefix tree (aka trie). - O (kn)
2. Para cada posición en la matriz, busque las cuerdas hacia arriba y hacia abajo en el trie. - O (m ³)

Tiempo total: O (max (kn, m ³))

En realistas de palabras búsquedas, la longitud media de las palabras encontrado en la matriz es más como k que como m, por lo que el tiempo necesario sería O (k max (n, m ²)).

Answer 3

¿Qué problema tenía tu respuesta?

• Un diccionario está ordenada por lo que creo que me arregle las palabras del diccionario en un prefix trie. Esto ayudaría ya que probablemente haya muchas palabras donde el prefijo también es una palabra. La clasificación ayuda (mínimamente) con el tiempo de compilación.

• Luego, recorra el crucigrama mirando todas las palabras posibles.A medida que extrae los caracteres de una palabra potencial, está caminando por el trie, por lo que encontrará la primera palabra que comienza con un cierto conjunto de caracteres, pero también estará en el lugar correcto para continuar encontrando otras palabras que comiencen con el mismo caracteres

Answer 4

La solución más adecuada depende en gran medida de las limitaciones que espera enfrentar. ¿Qué tan grande es tu diccionario? ¿Qué tan grande es tu crucigrama?

Sugiero echar un vistazo a Suffix trees. Puede insertar todas las palabras del diccionario en una. Luego busca en el árbol de sufijos las filas, columnas y diagonales. Para las filas, inicie una búsqueda desde la raíz del árbol para la primera letra de cada fila e itere a través del árbol a medida que pasa por la fila. Haz lo mismo de derecha a izquierda si es necesario. Una historia similar para columnas y diagonales.

La construcción del árbol es O (N) y consume O (N) espacio, donde N es el tamaño de su diccionario en caracteres. La búsqueda tomará tiempo O (PQ), donde su crucigrama es de tamaño PxQ. Dando un tiempo de ejecución general de O (N + PQ) y espacio de O (N).

Lo que pasa es que los árboles de sufijo son difíciles de implementar. Ellos realmente son. Por lo tanto es posible que prefiera conformarse con un simple Trie, que le dará un tiempo de ejecución total de O (N + PQ (max (P, Q)).

Answer 5

Esta pregunta es exactamente cómo se podría jugar Boggle.

el pasado cuestión en la más que suficientemente ANSWERS THIS QUESTION.

divertirse ...

Answer 6

me compilar el diccionario en un DFA que reconoce las palabras en el diccionario, y luego correr por encima de las filas y columnas y diagonales de la carta matriz. Debe ser O(m+n) donde m es la longitud del diccionario en caracteres y n es el área (w * h) de la matriz.