Eliminar subdirectorios de un sistema de archivos

Dada una array de strings arr[] que consta de N directorios únicos en forma de strings, la tarea es eliminar todos los subdirectorios e imprimir la array final.

Un directorio S es un subdirectorio si existe algún directorio D tal que S sea el prefijo de D.

Ejemplos:

Entrada: arr[] = {“/a”, “/a/j”, “/c/d/e”, “/c/d”, “/b”}
Salida: { “/a”, “/ c/d”, “/b”}
Explicación: El directorio “/a/j” es un subdirectorio del directorio “/a”, y “/c/d/e” es un subdirectorio del directorio “/c/d”.
Por lo tanto, elimine ambos.

Entrada: arr[] ={“/a”, “/a/b”, “/a/b/c”, “/a/b/c/d”}
Salida: {“/a”}
Explicación: Todo directorios son subdirectorios de “/a”

Enfoque ingenuo: el enfoque más simple es recorrer la array para verificar cada string, si existe una string que lo tenga como prefijo y eliminar dichas strings de la array. 

Complejidad de tiempo: O(len * N ² ) , donde len es la longitud de la string más larga de la array.
Espacio Auxiliar: O(N)

Enfoque eficiente: la idea es ordenar la array dada y comparar el directorio actual en la posición i con el directorio anterior en el índice (i -1) . Si arr[i – 1] es el prefijo de arr[i] , elimine arr[i] . Después de verificar toda la array, imprima los directorios restantes. Siga los pasos a continuación para resolver el problema:

• Ordene todos los directorios alfabéticamente e inicialice un vector res .
• Inserte el primer directorio en res .
• Verifique cada directorio con el último directorio válido, es decir, el último directorio desde res .
• El directorio no es válido (subdirectorio) si es igual a algún prefijo del directorio válido anterior. De lo contrario es válido.
• Si el directorio actual es válido, agréguelo a res .
• Imprime todos los directorios presentes en res después de realizar el recorrido.

A continuación se muestra la implementación del enfoque anterior:

// C++ program for the above approach
 
#include <bits/stdc++.h>
using namespace std;
 
// Function to remove sub-directories
// from the given lists dir
void eraseSubdirectory(vector<string>& dir)
{
    // Store final result
    vector<string> res;
 
    // Sort the given directories
    sort(dir.begin(), dir.end());
 
    // Insert 1st directory
    res.push_back(dir[0]);
 
    cout << "{" << dir[0] << ", ";
 
    // Iterating in directory
    for (int i = 1; i < dir.size(); i++) {
 
        // Current directory
        string curr = dir[i];
 
        // Our previous valid directory
        string prev = res.back();
 
        // Find length of previous directory
        int l = prev.length();
 
        // If subdirectory is found
        if (curr.length() > l && curr[l] == '/'
            && prev == curr.substr(0, l))
            continue;
 
        // Else store it in result
        // valid directory
        res.push_back(curr);
 
        cout << curr << ", ";
    }
 
    cout << "}\n";
}
 
// Driver Code
int main()
{
    // Given lists of directories dir[]
    vector<string> dir
        = { "/a", "/a/j", "/c/d/e",
            "/c/d", "/b" };
 
    // Function Call
    eraseSubdirectory(dir);
 
    return 0;
}

// Java program for the above approach
import java.io.*;
import java.util.*;
 
class GFG{
 
// Function to remove sub-directories
// from the given lists dir
static void eraseSubdirectory(ArrayList<String> dir)
{
     
    // Store final result
    ArrayList<String> res = new ArrayList<String>();
 
    // Sort the given directories
    Collections.sort(dir);
 
    // Insert 1st directory
    res.add(dir.get(0));
 
    System.out.print("{" + dir.get(0) + ", ");
 
    // Iterating in directory
    for(int i = 1; i < dir.size(); i++)
    {
         
        // Current directory
        String curr = dir.get(i);
 
        // Our previous valid directory
        String prev = res.get(res.size() - 1);
 
        // Find length of previous directory
        int l = prev.length();
 
        // If subdirectory is found
        if (curr.length() > l &&
           curr.charAt(l) == '/' &&
           prev.equals(curr.substring(0, l)))
            continue;
 
        // Else store it in result
        // valid directory
        res.add(curr);
 
        System.out.print(curr + ", ");
    }
    System.out.print("}\n");
}
 
// Driver Code
public static void main(String[] args)
{
     
    // Given lists of directories dir[]
    ArrayList<String> dir = new ArrayList<String>(Arrays.asList(
            "/a", "/a/j", "/c/d/e", "/c/d", "/b"));
 
    // Function Call
    eraseSubdirectory(dir);
}
}
 
// This code is contributed by akhilsaini

# Python3 program for the above approach
 
# Function to remove sub-directories
# from the given lists dir
def eraseSubdirectory(dir):
     
    # Store final result
    res = []
 
    # Sort the given directories
    dir.sort()
 
    # Insert 1st directory
    res.append(dir[0])
 
    print("{", dir[0], end = ", ")
 
    # Iterating in directory
    for i in range(1, len(dir)):
         
        # Current directory
        curr = dir[i]
 
        # Our previous valid directory
        prev = res[len(res) - 1]
 
        # Find length of previous directory
        l = len(prev)
 
        # If subdirectory is found
        if (len(curr) > l and
           curr[l] == '/' and
              prev == curr[:l]):
            continue
 
        # Else store it in result
        # valid directory
        res.append(curr)
        print(curr, end = ", ")
 
    print("}")
 
# Driver Code
if __name__ == '__main__':
 
    # Given lists of directories dir[]
    dir = [ "/a", "/a/j", "/c/d/e", "/c/d", "/b" ]
 
    # Function Call
    eraseSubdirectory(dir)
 
# This code is contributed by akhilsaini

// C# program for the above approach
using System;
using System.Collections;
 
class GFG{
 
// Function to remove sub-directories
// from the given lists dir
static void eraseSubdirectory(ArrayList dir)
{
     
    // Store final result
    ArrayList res = new ArrayList();
 
    // Sort the given directories
    dir.Sort();
 
    // Insert 1st directory
    res.Add(dir[0]);
 
    Console.Write("{" + dir[0] + ", ");
 
    // Iterating in directory
    for(int i = 1; i < dir.Count; i++)
    {
         
        // Current directory
        string curr = (string)dir[i];
 
        // Our previous valid directory
        string prev = (string)res[(res.Count - 1)];
 
        // Find length of previous directory
        int l = prev.Length;
 
        // If subdirectory is found
        if (curr.Length > l && curr[l] == '/' &&
            prev.Equals(curr.Substring(0, l)))
            continue;
 
        // Else store it in result
        // valid directory
        res.Add(curr);
 
        Console.Write(curr + ", ");
    }
    Console.Write("}\n");
}
 
// Driver Code
public static void Main()
{
     
    // Given lists of directories dir[]
    ArrayList dir = new ArrayList(){ "/a", "/a/j",
                                     "/c/d/e",
                                     "/c/d", "/b" };
 
    // Function Call
    eraseSubdirectory(dir);
}
}
 
// This code is contributed by akhilsaini

{/a, /b, /c/d, }

Complejidad de tiempo: O(N*log N)
Espacio auxiliar: O(N)