Algoritmi: găsirea celui mai lung prefix comun

Pentru blogul meu de astăzi, voi lucra printr-un algoritm pentru a găsi cel mai lung prefix comun într-un șir între o serie de șiruri. Am întâlnit recent această problemă pe Leet Code și am vrut să împărtășesc soluția mea și cum am ajuns la răspunsul meu. Deci, să intrăm direct în ea!

Toate exemplele vor fi realizate în JavaScript!

Întrebare

Întrebarea este următoarea:

Scrieți o funcție pentru a găsi cel mai lung șir de prefixuri comune dintr-o serie de șiruri.

Dacă nu există un prefix comun, returnați un șir gol & quot; & quot; .

Exemplul 1

Intrare = & gt; [„flori”, „curgere”, „a zburat”]
Ieșire = & gt; fl

Exemplul 2

Intrare = & gt; [„Racecar”, „scooter”, „bat”]
Ieșire = & gt; „”

Ce este un prefix?

Când abordați l această problemă, doriți să fiți sigur că înțelegeți întrebarea care este pusă. Primul lucru pe care ți-l poți întreba este: Ce este un prefix? . Definiția Google afirmă că un prefix este „ un cuvânt, o literă sau un număr plasat înaintea altuia ”. De exemplu, dacă ar fi să ne uităm la matricea de mai sus și să scoatem un cuvânt ca „flori”, litera care începe cuvântul este „f”, ceea ce înseamnă că „f” este prefixul „flori”.

Rezolvarea pentru cel mai lung prefix comun

Când rezolvați această întrebare, există 2 metode comune pentru rezolvarea acestei probleme:

Ambii algoritmi au exact aceeași complexitate de timp și spațiu. Dar metoda verticală este mai rapidă în rezolvarea problemei în cel mai rău caz. Să aruncăm o privire la un exemplu foarte inventat în care aveți o serie de sute de cuvinte și toate cuvintele sunt exact aceleași, cu excepția ultimului. Utilizarea metodei orizontale înseamnă că trebuie să faceți o comparație de 99 de ori înainte de a ajunge în cele din urmă la ultimul cuvânt și de a realiza că nu există un prefix comun. Dar cu metoda verticală tot ce trebuie să faceți este să parcurgeți prima literă a fiecărui cuvânt și să vă dați seama imediat că nu există un prefix comun.

Soluție

Voi folosi metoda verticală, deoarece este cea mai eficientă pentru acest algoritm.

Ceea ce am vrea mai întâi să facem este să ne creăm funcția:

În interiorul funcției noastre anonime dorim să creăm o variabilă pe care o vom folosi pentru a echivala cu cel mai lung prefix și pentru a fi returnată la final funcția noastră:

Acum trebuie să luăm în considerare faptul că o matrice poate fi fie goală sau să aibă o valoare nulă ca mai jos:

Dacă acesta este cazul, atunci am dori să creăm o declarație if pentru a explica acest lucru la începutul funcției noastre:

Deoarece acum avem direcțiile noastre drepte, putem itera prin matrice pentru a începe să comparăm două cuvinte la rând. Pentru ca acest lucru să se întâmple, dorim, de asemenea, să începem de la primul cuvânt al matricei noastre:

Pentru a compara primele noastre șiruri de caractere, trebuie să creăm o buclă imbricată pentru … care începe de la următorul șir din matricea noastră. În interiorul acestei bucle noi pentru …, vom compara apoi prefixul șirului de secunde cu variabila char pe care am creat-o (Scope ne permite să folosim orice variabilă în cele mai exterioare zone ale funcției noastre!). Dacă prefixul din al doilea șir nu este egal cu char , atunci ne returnăm prefixul, întrerupându-ne astfel funcția. Cu toate acestea, dacă cele două prefixe sunt egale, continuăm cu ultima noastră parte a funcției noastre, care adaugă următorul char și prefixul actual împreună.

Sper că ați găsit acest articol util în rezolvarea acestui algoritm folosind metoda orizontală!