Maison  >  Article  >  développement back-end  >  Supprimer les sous-dossiers du système de fichiers

Supprimer les sous-dossiers du système de fichiers

Barbara Streisand
Barbara Streisandoriginal
2024-10-31 04:35:01476parcourir

Remove Sub-Folders from the Filesystem

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 <= dossier.length <= 4 * 104
  • 2 <= dossier[i].length <= 100
  • 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






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!

Déclaration:
Le contenu de cet article est volontairement contribué par les internautes et les droits d'auteur appartiennent à l'auteur original. Ce site n'assume aucune responsabilité légale correspondante. Si vous trouvez un contenu suspecté de plagiat ou de contrefaçon, veuillez contacter admin@php.cn