Ermitteln Sie die Länge des längsten gemeinsamen Präfixes

3043. Finden Sie die Länge des längsten gemeinsamen Präfixes

Schwierigkeit:Mittel

Themen:Array, Hash-Tabelle, String, Trie

Sie erhalten zwei Arrays mit positiven ganzen Zahlen arr1 und arr2.

Ein Präfix einer positiven Ganzzahl ist eine Ganzzahl, die aus einer oder mehreren ihrer Ziffern besteht, beginnend mit der Ziffer ganz links. Beispielsweise ist 123 ein Präfix der Ganzzahl 12345, während 234 nicht.

ist

Ein gemeinsames Präfix zweier Ganzzahlen a und b ist eine Ganzzahl c, sodass c ein Präfix sowohl von a als auch von b ist. Beispielsweise haben 5655359 und 56554 ein gemeinsames Präfix 565, während 1223 und 43456 keinein gemeinsames Präfix haben.

Sie müssen die Länge des längsten gemeinsamen Präfixes zwischen allen Ganzzahlpaaren (x, y) ermitteln, sodass x zu arr1 und y zu arr2 gehört.

Gibt die Länge des längsten gemeinsamen Präfixes aller Paare zurück. Wenn zwischen ihnen kein gemeinsames Präfix vorhanden ist, geben Sie 0 zurück.

Beispiel 1:

• Eingabe: arr1 = [1,10,100], arr2 = [1000]
• Ausgabe: 3
• Erklärung: Es gibt 3 Paare (arr1[i], arr2[j]):
  • Das längste gemeinsame Präfix von (1, 1000) ist 1.
  • Das längste gemeinsame Präfix von (10, 1000) ist 10.
  • Das längste gemeinsame Präfix von (100, 1000) ist 100.
  • Das längste gemeinsame Präfix ist 100 mit einer Länge von 3.

Beispiel 2:

• Eingabe: arr1 = [1,2,3], arr2 = [4,4,4]
• Ausgabe: 4
• Erklärung: Es gibt kein gemeinsames Präfix für jedes Paar (arr1[i], arr2[j]), daher geben wir 0 zurück.
  • Beachten Sie, dass gemeinsame Präfixe zwischen Elementen desselben Arrays nicht zählen.

Einschränkungen:

• 1 <= arr1.length, arr2.length <= 5 * 10⁴
• 1 <= arr1[i], arr2[i] <= 10⁸

Hinweis:

1. Fügen Sie alle möglichen Präfixe jedes Elements in arr1 in ein HashSet ein.
2. Überprüfen Sie für alle möglichen Präfixe jedes Elements in arr2, ob es im HashSet vorhanden ist.

Lösung:

Wir können ein HashSet verwenden, um die Präfixe aus einem Array zu speichern und dann im zweiten Array nach diesen Präfixen zu suchen.

Ansatz:

1. Präfixe generieren: Generieren Sie für jede Zahl in arr1 und arr2 alle möglichen Präfixe. Ein Präfix besteht aus einer oder mehreren Ziffern, beginnend mit der Ziffer ganz links.

2. Präfixe von arr1 in einem Set speichern: Die Verwendung eines HashSets zum Speichern aller Präfixe von Zahlen in arr1 gewährleistet schnelle Suchvorgänge bei der Überprüfung von Präfixen von arr2.

3. Längstes gemeinsames Präfix finden: Generieren Sie für jede Zahl in arr2 ihre Präfixe und prüfen Sie, ob eines dieser Präfixe im HashSet aus Schritt 2 vorhanden ist. Verfolgen Sie das längste gefundene Präfix.

4. Die Länge des längsten gemeinsamen Präfixes zurückgeben: Wenn ein gemeinsames Präfix gefunden wird, wird dessen Länge zurückgegeben; andernfalls 0 zurückgeben.

Lassen Sie uns diese Lösung in PHP implementieren: 3043. Finden Sie die Länge des längsten gemeinsamen Präfixes

  
  
  Erläuterung:




HashSet-Erstellung:


Wir erstellen zunächst ein assoziatives Array $prefixSet, um alle möglichen Präfixe von Zahlen in arr1 zu speichern.
Wir durchlaufen jede Zahl in arr1, konvertieren sie in einen String und extrahieren alle ihre Präfixe mit der Funktion substr. Jedes Präfix wird im $prefixSet.
 gespeichert



Präfixprüfung:


Als nächstes durchlaufen wir jede Zahl in arr2 und wandeln sie ebenfalls in einen String um.
Für jede Zahl in arr2 extrahieren wir erneut alle möglichen Präfixe.
Wenn in $prefixSet ein Präfix vorhanden ist, prüfen wir, ob seine Länge größer als die aktuell gefundene maximale Länge ($maxLength) ist.



Ergebnis zurückgeben:


Schließlich geben wir die Länge des längsten gefundenen gemeinsamen Präfixes zurück.





  
  
  Komplexität:




Zeitkomplexität: O(n * m) wobei n und m die Längen von arr1 bzw. arr2 sind. Dies liegt daran, dass wir jede Nummer und ihre Präfixe verarbeiten.

Raumkomplexität: O(p), wobei p die Gesamtzahl der im HashSet gespeicherten Präfixe ist.


Diese Lösung ist effizient und funktioniert gut innerhalb der vorgegebenen Einschränkungen.

Kontaktlinks
Wenn Sie diese Serie hilfreich fanden, denken Sie bitte darüber nach, dem Repository einen Stern auf GitHub zu geben oder den Beitrag in Ihren bevorzugten sozialen Netzwerken zu teilen? Ihre Unterstützung würde mir sehr viel bedeuten!

Wenn Sie weitere hilfreiche Inhalte wie diesen wünschen, folgen Sie mir gerne:


LinkedIn
GitHub



          

            
  

            
        
Das obige ist der detaillierte Inhalt vonErmitteln Sie die Länge des längsten gemeinsamen Präfixes. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!