Dato una matrice bidimensionale di alfabeti, cerca la parola data in tutte le direzioni. Di seguito è riportato un esempio per cercare la parola "TEAM" :
Il numero di occorrenze è 4 nella matrice di seguito.
Qual è l'approccio migliore per risolverlo? Non è una parola del dizionario. La sua semplice sequenza di ricerca in tutte le direzioni.
Ho fatto qualcosa di simile tempo fa. Dovresti approfittare del fatto che le parole sono un insieme ordinato di personaggi. Quindi, esegui una ricerca lineare sulla matrice per la prima lettera, quindi chiamerai in modo ricorsivo la ricerca direzionale.
Per semplificare la complessità computazionale, puoi aggiungere alcuni vincoli, ad esempio if word.length > number of characters on that direction don't start searching .
La firma della funzione ricorsiva sarebbe come:
boolean search(string word, int direction)
con caso terminale
if (word.length==1) return isNextLetterInDirection(word, direction);
e la ricerca è
search(substring(word, 0, word.length-1), direction);
Questo algoritmo copre anche casi e parole palindromo incluse le loro sillabe.
Puoi utilizzare il backtracking per risolvere questo problema, procedi fino a trovare la parola che completa il resto del backtrack.
Mentre procedi, c'è un vincolo che procede nella stessa direzione con cui hai iniziato.
Ad esempio se stai andando su "UP", quindi dal prossimo personaggio dovresti andare su "UP" Only.
Leggi altre domande sui tag algorithms