Tengo una matriz 2D de caracteres aleatorios. Quiero hacer coincidir patrones específicos de estos caracteres: ej .: ABA, BACKA, subir/bajar/izquierda/derecha. ¿Cuál es el mejor algoritmo para encontrar este patrón?La mejor manera de encontrar un patrón específico en una matriz 2D
Si esto es como una búsqueda de palabras, solo puede ir en una dirección (una vez que comience a la izquierda, solo puede seguir hacia la izquierda), la respuesta debería ser bastante simple, simplemente pruebe cada inicio posible ubicación e ir en cada dirección. En el peor de los casos, será O (mn^2) para n by n Si puede subir/izquierda/etc. en cualquier número de ocasiones, la forma más obvia es tratar la matriz como un gráfico y hacer un BFS o DFS. Dependiendo del tamaño de la palabra y la distribución de las letras, esto puede ser muy costoso.
Si tenía varias consultas para una matriz única, ambos métodos podrían acelerarse almacenando en caché las palabras generadas en una estructura tipo trie con referencias a las celdas originales.
Gracias. El número de palabras que necesito para que coincida también es muy grande. Para una matriz grande y una gran cantidad de palabras, la búsqueda es lenta y los requisitos de memoria caché también aumentan significativamente. Cualquier optimizaciones? – Swami
¿Esto es una pregunta de la entrevista? –
¿Es esta tarea? En caso afirmativo, márquelo como tal. –
Esta no es una pregunta de entrevista y esta no es tarea. – Swami