Given an array of strings arr[] consisting of N unique directories in the form of strings, the task is to remove all the subdirectories and print the final array.
A directory S is a subdirectory if there exists any directory D such that S is the prefix of D.
Examples:
Input: arr[] = {“/a”, “/a/j”, “/c/d/e”, “/c/d”, “/b”}
Output: { “/a”, “/c/d”, “/b”}
Explanation: Directory “/a/j” is a subdirectory of directory “/a”, and “/c/d/e” is a subdirectory of directory “/c/d”.
Therefore, remove both of them.Input: arr[] = {“/a”, “/a/b”, “/a/b/c”, “/a/b/c/d”}
Output: {“/a”}
Explanation: All directories are subdirectories of “/a”
Naive Approach: The simplest approach is to traverse the array to check for each string, if there exists a string having it as the prefix and remove such strings from the array.
Time Complexity: O(len * N2), where len is the length of the longest string in the array.
Auxiliary Space: O(N)
Efficient Approach: The idea is to sort the given array and compare the current directory at position i with the previous directory at index (i -1). If arr[i – 1] is the prefix of arr[i] then remove arr[i]. After checking the whole array, print the remaining directories. Follow the below steps to solve the problem:
- Sort all the directories alphabetically and initialize a vector res.
- Insert the first directory into res.
- Check each directory with the last valid directory i.e., last directory from res.
- The directory is invalid(sub-directory) if it equals to some prefix of the previous valid directory. Else it is valid.
- If the current directory is valid, then add it to res.
- Print all the directories present in res after done traversing.
Below is the implementation of the above approach:
C++
// C++ program for the above approach#include <bits/stdc++.h>using namespace std;// Function to remove sub-directories// from the given lists dirvoid 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 Codeint 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
// Java program for the above approachimport java.io.*;import java.util.*;class GFG{// Function to remove sub-directories// from the given lists dirstatic 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 Codepublic 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
# Python3 program for the above approach# Function to remove sub-directories# from the given lists dirdef 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 Codeif __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#
// C# program for the above approachusing System;using System.Collections;class GFG{// Function to remove sub-directories// from the given lists dirstatic 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 Codepublic 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 |
Javascript
// Javascript program for the above approach// Function to remove sub-directories// from the given lists dirfunction eraseSubdirectory(dir) { // Store final result let res = new Array(); // Sort the given directories dir.sort(); // Insert 1st directory res.push(dir[0]); console.log("{" + dir[0] + ", "); // Iterating in directory for (let i = 1; i < dir.length; i++) { // Current directory let curr = dir[i]; // Our previous valid directory let prev = res[res.length - 1]; // Find length of previous directory let l = prev.length; // If subdirectory is found if (curr.length > l && curr[l] == '/' && (prev == (curr.substring(0, l)))) continue; // Else store it in result // valid directory res.push(curr); console.log(curr + ", "); } console.log("}\n");}// Driver Code// Given lists of directories dir[]let dir = ["/a", "/a/j", "/c/d/e", "/c/d", "/b"];// Function CalleraseSubdirectory(dir);// This code is contributed by Saurabh Jaiswal |
Output:
{/a, /b, /c/d, }
Time Complexity: O(N*log N)
Auxiliary Space: O(N)
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
