Ricerca di un "ago" in un due "pagliaio" dimensionale

Immagino che questa sia una delle domande più frequenti dell'intervista, tuttavia non sono in grado di risolverlo in modo efficiente (significato efficiente minore complessità temporale e uso di un adeguata struttura dati). Il problema è questo: Se c'è un m x n matrix di caratteri (dire pagliaio) e una data stringa char di lunghezza k (l'ago). Scrivi un programma per verificare se il pagliaio contiene l'ago. Tieni presente che dobbiamo cercare nel pagliaio solo dall'alto verso il basso o da sinistra a destra. Ad esempioRicerca di un "ago" in un due "pagliaio" dimensionale

Haystack 

ahydsfd 
sdflddl 
dfdfd 
dfdl 
uifddffdhc 

Needle: 
hdffi 

Output: 
Yes Found!!

fonte

2012-03-01 hytriutucx

Cosa c'è di sbagliato nella ricerca della formica da sinistra a destra dall'alto verso il basso separatamente? –

Mi è stato detto da due intervistatori consecutivi che esiste un approccio migliore. Non sono sicuro, "migliore" in che senso intendevano. – hytriutucx

@ javacoder990: non hai chiesto agli intervistatori cosa volevano dire? –

La nautezza bruta è O (m * n * k). Ecco alcune idee per l'ottimizzazione.

Ricerca singolo
Invece di fare una ricerca di orizzontali e poi un altro per mercati verticali, fare entrambe le cose contemporaneamente. Ogni volta che trovi una ricorrenza della prima lettera dell'ago, cerca una corrispondenza orizzontale e verticale che inizi a quella lettera. Ciò non migliorerà la complessità, ma in molti casi questo potrebbe dimezzare il tempo dal momento che vedrai solo le partenze sbagliate una volta.

rare lettere
Invece di cercare per la prima lettera dell'ago, cercare la lettera più raro che si verifica nel ago. Questo escluderà molte delle possibili partite. Per determinare quali lettere sono più rare scansionare l'intera scheda o utilizzare il campionamento casuale.

String efficiente Ricerca
Usa una migliore string searching algorithm come Knuth–Morris–Pratt. Cerca ogni riga e ogni colonna individualmente usando l'algoritmo. La mia scommessa è che questo è ciò che gli intervistatori cercano, dal momento che riduce la complessità a O (m * n).

Exploit righe brevi
ho notato che non tutte le righe hanno la stessa lunghezza. Quando cerchi le corrispondenze verticali, puoi interrompere la ricerca su quella riga non appena l'ago esce dal sacco, poiché anche gli aghi più avanti lungo la fila usciranno dal sacco e quindi non possono essere abbinati.

fonte

2012-03-01 12:46:53 tom

Determinare le lettere più rare di un'intera scansione significherebbe che visiti ogni cella, che nella maggior parte dei casi è la maggior parte del lavoro, ad eccezione di una scheda che contiene quasi solo - ad esempio - "d" e l'ago inizia con d e consiste per lo più di "d's". Ma senza ulteriore conoscenza (anche la distribuzione di caratteri, caratteri di un token da un testo in linguaggio x, ...) sul testo, l'analisi del testo potrebbe richiedere più tempo del semplice avvio del lavoro. Finché non si conosce la dimensione della matrice, anche un campione casuale di 100 caratteri potrebbe non essere disponibile. Né lo sappiamo, se è rappresentativo. –

Il metodo di forza bruta avrà peggiore complessità temporale m * n.That è se l'ago è singolo carattere e si inizia l'analisi riga di matrice o per colonna saggio.

fonte

2012-03-01 10:10:10 mawia

Ovviamente se l'ago ha lunghezza di carattere x, può essere ottimizzato per avere la complessità di (m-x-1) * n! – mawia

Il problema è con gli aghi più lunghi. –

È possibile limitare la ricerca del primo carattere a colonne n-k e righe m-k. Una volta trovato, 2 (k-1) i confronti sono necessari per la risposta.

fonte

2012-03-01 13:06:51 CapelliC

Ricerca di un "ago" in un due "pagliaio" dimensionale

risposta

Problemi correlati