Unterordner aus dem Dateisystem entfernen

1233. Unterordner aus dem Dateisystem entfernen

Schwierigkeit:Mittel

Themen: Array, String, Tiefensuche, Versuch

Geben Sie bei einer gegebenen Ordnerliste die Ordner zurück, nachdem Sie alle Unterordner in diesen Ordnern entfernt haben. Sie können die Antwort in beliebiger Reihenfolge zurücksenden.

Wenn sich ein Ordner[i] in einem anderen Ordner[j] befindet, wird er als Unterordner davon bezeichnet. Ein Unterordner von Ordner[j] muss mit Ordner[j] beginnen, gefolgt von einem „/“. Beispielsweise ist „/a/b“ ein Unterordner von „/a“, aber „/b“ ist kein Unterordner von „/a/b/c“.

Das Format eines Pfads besteht aus einer oder mehreren verketteten Zeichenfolgen der Form: „/“, gefolgt von einem oder mehreren englischen Kleinbuchstaben.

• Zum Beispiel sind „/leetcode“ und „/leetcode/problems“ gültige Pfade, eine leere Zeichenfolge und „/“ hingegen nicht.

Beispiel 1:

• Eingabe: Ordner = ["/a",/a/b",/c/d",/c/d/e",/c/f"]
• Ausgabe: ["/a","/c/d","/c/f"]
• Erklärung: Der Ordner „/a/b“ ist ein Unterordner von „/a“ und „/c/d/e“ befindet sich im Ordner „/c/d“ in unserem Dateisystem.

Beispiel 2:

• Eingabe: Ordner = ["/a","/a/b/c","/a/b/d"]
• Ausgabe: ["/a"]
• Erklärung: Die Ordner „/a/b/c“ und „/a/b/d“ werden entfernt, da es sich um Unterordner von „/a“ handelt.

Beispiel 3:

• Eingabe: Ordner = ["/a/b/c","/a/b/ca","/a/b/d"]
• Ausgabe: ["/a/b/c","/a/b/ca","/a/b/d"]

Einschränkungen:

• 1 4
• 2
• Ordner[i] enthält nur Kleinbuchstaben und „/“.
• Ordner[i] beginnt immer mit dem Zeichen „/“.
• Jeder Ordnername ist einzigartig.

Hinweis:

1. Ordner lexikografisch sortieren.
2. Fügen Sie das aktuelle Element in ein Array ein und wiederholen Sie die Schleife, bis alle Unterordner entfernt sind. Wiederholen Sie dies, bis kein Element mehr übrig ist.

Lösung:

Wir können eine Kombination aus Sortierung und String-Vergleich verwenden. Die folgenden Schritte beschreiben eine Lösung in PHP:

1. Ordner lexikografisch sortieren: Durch das Sortieren der Ordnerpfade in lexikografischer Reihenfolge wird sichergestellt, dass jeder Unterordner sofort seinem übergeordneten Ordner folgt. Auf „/a“ folgt beispielsweise in der sortierten Liste „/a/b“, sodass wir problemlos nach Unterordnerbeziehungen suchen können.

2. Unterordner identifizieren und herausfiltern: Wir können die sortierte Liste durchlaufen und prüfen, ob der aktuelle Ordnerpfad ein Unterordner des zuvor hinzugefügten Pfads ist. Wenn ja, überspringen wir es. Wenn nicht, fügen wir es unserer Ergebnisliste hinzu.

3. Implementieren Sie die Lösung in PHP: Wir verfolgen den letzten zur Ergebnisliste hinzugefügten Ordnerpfad. Wenn der aktuelle Ordner mit diesem letzten Ordner beginnt und unmittelbar ein / folgt, handelt es sich um einen Unterordner und sollte ignoriert werden.

Lassen Sie uns diese Lösung in PHP implementieren: 1233. Unterordner aus dem Dateisystem entfernen

<?php /**
 * @param String[] $folder
 * @return String[]
 */
function removeSubfolders($folders) {
    ...
    ...
    ...
    /**
     * go to ./solution.php
     */
}

// Test cases
$folder1 = ["/a","/a/b","/c/d","/c/d/e","/c/f"];
$folder2 = ["/a","/a/b/c","/a/b/d"];
$folder3 = ["/a/b/c","/a/b/ca","/a/b/d"];

print_r(removeSubfolders($folder1)); // Output: ["/a","/c/d","/c/f"]
print_r(removeSubfolders($folder2)); // Output: ["/a"]
print_r(removeSubfolders($folder3)); // Output: ["/a/b/c","/a/b/ca","/a/b/d"]
?>

Erläuterung:

1. Sortierung: Die Funktion sort() ordnet Ordner in lexikografischer Reihenfolge an. Dies erleichtert das Auffinden von Unterordnerbeziehungen, da Unterordner direkt auf ihre übergeordneten Ordner folgen.

2. Durchlaufen Sie jeden Ordner:

   • Wenn das Ergebnis leer ist (erste Iteration) oder wenn der aktuelle Ordnerpfad nicht mit dem zuletzt hinzugefügten Ordner gefolgt von einem / beginnt, ist es kein Unterordner und wird dem Ergebnisarray hinzugefügt.
   • Wenn es mit dem letzten Ordnerpfad beginnt und unmittelbar darauf ein / folgt, handelt es sich um einen Unterordner und wir überspringen das Hinzufügen zum Ergebnis.

3. Ergebnis: Die Funktion gibt ein Ergebnis zurück, das nur die Stammordner enthält, ausgenommen etwaige Unterordner.

Dieser Ansatz ist effizient mit einer zeitlichen Komplexität von O(n log n) aufgrund des Sortierschritts und der lineare Scan hat O(n). ), was dies zu einer guten Lösung für größere Eingaben innerhalb der Einschränkungen des Problems macht.

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 vonUnterordner aus dem Dateisystem entfernen. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!