Supprimer les sous-dossiers du système de fichiers

1233. Supprimer les sous-dossiers du système de fichiers

Difficulté :Moyen

Sujets :Array, String, Depth-First Search, Trie

Étant donné une liste de dossiers, renvoyez les dossiers après avoir supprimé tous les sous-dossiers dans ces dossiers. Vous pouvez renvoyer la réponse dans n'importe quel ordre.

Si un dossier[i] se trouve dans un autre dossier[j], il est appelé un sous-dossier de celui-ci. Un sous-dossier du dossier[j] doit commencer par dossier[j], suivi d'un "/". Par exemple, "/a/b" est un sous-dossier de "/a", mais "/b" n'est pas un sous-dossier de "/a/b/c".

Le format d'un chemin est une ou plusieurs chaînes concaténées de la forme : '/' suivie d'une ou plusieurs lettres anglaises minuscules.

• Par exemple, "/leetcode" et "/leetcode/problems" sont des chemins valides alors qu'une chaîne vide et "/" ne le sont pas.

Exemple 1 :

• Entrée : dossier = ["/a","/a/b","/c/d","/c/d/e","/c/f"]
• Sortie : ["/a","/c/d","/c/f"]
• Explication : Les dossiers "/a/b" sont un sous-dossier de "/a" et "/c/d/e" se trouvent à l'intérieur du dossier "/c/d" dans notre système de fichiers.

Exemple 2 :

• Entrée : dossier = ["/a","/a/b/c","/a/b/d"]
• Sortie : ["/a"]
• Explication : Les dossiers "/a/b/c" et "/a/b/d" seront supprimés car ce sont des sous-dossiers de "/a".

Exemple 3 :

• Entrée : dossier = ["/a/b/c","/a/b/ca","/a/b/d"]
• Sortie : ["/a/b/c","/a/b/ca","/a/b/d"]

Contraintes :

• 1 4
• 2
• le dossier[i] ne contient que des lettres minuscules et '/'.
• dossier[i] commence toujours par le caractère '/'.
• Chaque nom de dossier est unique.

Indice :

1. Trier les dossiers lexicographiquement.
2. Insérez l'élément actuel dans un tableau, puis bouclez jusqu'à ce que nous nous débarrassions de tous leurs sous-dossiers, répétez cette opération jusqu'à ce qu'il ne reste plus aucun élément.

Solution :

Nous pouvons utiliser une combinaison de tri et de comparaison de chaînes. Les étapes ci-dessous décrivent une solution en PHP :

1. Trier les dossiers lexicographiquement : Le tri des chemins de dossier par ordre lexicographique garantit que tout sous-dossier suivra immédiatement son dossier parent. Par exemple, "/a" sera suivi de "/a/b" dans la liste triée, ce qui nous permettra de vérifier facilement les relations entre les sous-dossiers.

2. Identifier et filtrer les sous-dossiers : Nous pouvons parcourir la liste triée, en vérifiant si le chemin du dossier actuel est un sous-dossier du chemin précédemment ajouté. Si c'est le cas, nous l'ignorons. Sinon, nous l'ajoutons à notre liste de résultats.

3. Implémenter la solution en PHP : Nous gardons une trace du dernier chemin du dossier ajouté à la liste des résultats. Si le dossier actuel commence par ce dernier dossier et est immédiatement suivi d'un /, il s'agit d'un sous-dossier et doit être ignoré.

Implémentons cette solution en PHP : 1233. Supprimer les sous-dossiers du système de fichiers

<?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"]
?>

Explication:

1. Tri : La fonction sort() organise les dossiers par ordre lexicographique. Cela facilite la recherche des relations entre les sous-dossiers, car les sous-dossiers suivront directement leurs dossiers parents.

2. Parcourez chaque dossier :

   • Si le résultat est vide (première itération) ou si le chemin du dossier courant ne commence pas par le dernier dossier ajouté suivi d'un /, ce n'est pas un sous-dossier et est ajouté au tableau résultat.
   • S'il commence par le chemin du dernier dossier et est immédiatement suivi d'un /, il s'agit d'un sous-dossier et nous ignorons son ajout au résultat.

3. Résultat : La fonction renvoie le résultat, qui contient uniquement les dossiers racine, à l'exclusion des sous-dossiers.

Cette approche est efficace avec une complexité temporelle de O(n log n) en raison de l'étape de tri, et le balayage linéaire a O(n ), ce qui en fait une bonne solution pour des entrées plus importantes dans les limites du problème.

Liens de contact

Si vous avez trouvé cette série utile, pensez à donner une étoile au référentiel sur GitHub ou à partager la publication sur vos réseaux sociaux préférés ?. Votre soutien signifierait beaucoup pour moi !

Si vous souhaitez du contenu plus utile comme celui-ci, n'hésitez pas à me suivre :

• LinkedIn
• GitHub

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!