Question

1233. Remove Sub-Folders from the Filesystem

中文文档

Description

Given a list of folders folder, return _the folders after removing all sub-folders in those folders_. You may return the answer in any order.

If a folder[i] is located within another folder[j], it is called a sub-folder of it.

The format of a path is one or more concatenated strings of the form: '/' followed by one or more lowercase English letters.

• For example, "/leetcode" and "/leetcode/problems" are valid paths while an empty string and "/" are not.

 

Example 1:

Input: folder = ["/a","/a/b","/c/d","/c/d/e","/c/f"]
Output: ["/a","/c/d","/c/f"]
Explanation: Folders "/a/b" is a subfolder of "/a" and "/c/d/e" is inside of folder "/c/d" in our filesystem.

Example 2:

Input: folder = ["/a","/a/b/c","/a/b/d"]
Output: ["/a"]
Explanation: Folders "/a/b/c" and "/a/b/d" will be removed because they are subfolders of "/a".

Example 3:

Input: folder = ["/a/b/c","/a/b/ca","/a/b/d"]
Output: ["/a/b/c","/a/b/ca","/a/b/d"]

 

Constraints:

• 1 <= folder.length <= 4 * 104
• 2 <= folder[i].length <= 100
• folder[i] contains only lowercase letters and '/'.
• folder[i] always starts with the character '/'.
• Each folder name is unique.

Solutions

Solution 1: Sorting

First, we sort the array folder in lexicographical order, then traverse the array. For the current folder $f$ we are traversing, if its length is greater than or equal to the length of the last folder in the answer array, and its prefix includes the last folder in the answer array plus a /, then $f$ is a subfolder of the last folder in the answer array, and we don't need to add it to the answer array. Otherwise, we add $f$ to the answer array.

After the traversal ends, the folders in the answer array are the answer required by the problem.

The time complexity is $O(n \times \log n \times m)$, and the space complexity is $O(m)$. Where $n$ and $m$ are the length of the array folder and the maximum length of the strings in the array folder, respectively.

class Solution:
  def removeSubfolders(self, folder: List[str]) -> List[str]:
    folder.sort()
    ans = [folder[0]]
    for f in folder[1:]:
      m, n = len(ans[-1]), len(f)
      if m >= n or not (ans[-1] == f[:m] and f[m] == '/'):
        ans.append(f)
    return ans

class Solution {
  public List<String> removeSubfolders(String[] folder) {
    Arrays.sort(folder);
    List<String> ans = new ArrayList<>();
    ans.add(folder[0]);
    for (int i = 1; i < folder.length; ++i) {
      int m = ans.get(ans.size() - 1).length();
      int n = folder[i].length();
      if (m >= n
        || !(ans.get(ans.size() - 1).equals(folder[i].substring(0, m))
          && folder[i].charAt(m) == '/')) {
        ans.add(folder[i]);
      }
    }
    return ans;
  }
}

class Solution {
public:
  vector<string> removeSubfolders(vector<string>& folder) {
    sort(folder.begin(), folder.end());
    vector<string> ans = {folder[0]};
    for (int i = 1; i < folder.size(); ++i) {
      int m = ans.back().size();
      int n = folder[i].size();
      if (m >= n || !(ans.back() == folder[i].substr(0, m) && folder[i][m] == '/')) {
        ans.emplace_back(folder[i]);
      }
    }
    return ans;
  }
};

func removeSubfolders(folder []string) []string {
  sort.Strings(folder)
  ans := []string{folder[0]}
  for _, f := range folder[1:] {
    m, n := len(ans[len(ans)-1]), len(f)
    if m >= n || !(ans[len(ans)-1] == f[:m] && f[m] == '/') {
      ans = append(ans, f)
    }
  }
  return ans
}

Solution 2: Trie

We can use a trie to store all the folders in the array folder. Each node of the trie contains a children field, used to store the child nodes of the current node, and a fid field, used to store the index of the folder corresponding to the current node in the array folder.

For each folder $f$ in the array folder, we first split $f$ into several substrings according to /, then start from the root node and add the substrings to the trie in turn. Next, we start from the root node to search the trie. If the fid field of the current node is not -1, it means that the folder corresponding to the current node is a folder in the answer array. We add it to the answer array and return. Otherwise, we recursively search all child nodes of the current node and finally return the answer array.

The time complexity is $O(n \times m)$, and the space complexity is $O(n \times m)$. Where $n$ and $m$ are the length of the array folder and the maximum length of the strings in the array folder, respectively.

class Trie:
  def __init__(self):
    self.children = {}
    self.fid = -1

  def insert(self, i, f):
    node = self
    ps = f.split('/')
    for p in ps[1:]:
      if p not in node.children:
        node.children[p] = Trie()
      node = node.children[p]
    node.fid = i

  def search(self):
    def dfs(root):
      if root.fid != -1:
        ans.append(root.fid)
        return
      for child in root.children.values():
        dfs(child)

    ans = []
    dfs(self)
    return ans


class Solution:
  def removeSubfolders(self, folder: List[str]) -> List[str]:
    trie = Trie()
    for i, f in enumerate(folder):
      trie.insert(i, f)
    return [folder[i] for i in trie.search()]

class Trie {
  private Map<String, Trie> children = new HashMap<>();
  private int fid = -1;

  public void insert(int fid, String f) {
    Trie node = this;
    String[] ps = f.split("/");
    for (int i = 1; i < ps.length; ++i) {
      String p = ps[i];
      if (!node.children.containsKey(p)) {
        node.children.put(p, new Trie());
      }
      node = node.children.get(p);
    }
    node.fid = fid;
  }

  public List<Integer> search() {
    List<Integer> ans = new ArrayList<>();
    dfs(this, ans);
    return ans;
  }

  private void dfs(Trie root, List<Integer> ans) {
    if (root.fid != -1) {
      ans.add(root.fid);
      return;
    }
    for (var child : root.children.values()) {
      dfs(child, ans);
    }
  }
}

class Solution {
  public List<String> removeSubfolders(String[] folder) {
    Trie trie = new Trie();
    for (int i = 0; i < folder.length; ++i) {
      trie.insert(i, folder[i]);
    }
    List<String> ans = new ArrayList<>();
    for (int i : trie.search()) {
      ans.add(folder[i]);
    }
    return ans;
  }
}

class Trie {
public:
  void insert(int fid, string& f) {
    Trie* node = this;
    vector<string> ps = split(f, '/');
    for (int i = 1; i < ps.size(); ++i) {
      auto& p = ps[i];
      if (!node->children.count(p)) {
        node->children[p] = new Trie();
      }
      node = node->children[p];
    }
    node->fid = fid;
  }

  vector<int> search() {
    vector<int> ans;
    function<void(Trie*)> dfs = [&](Trie* root) {
      if (root->fid != -1) {
        ans.push_back(root->fid);
        return;
      }
      for (auto& [_, child] : root->children) {
        dfs(child);
      }
    };
    dfs(this);
    return ans;
  }

  vector<string> split(string& s, char delim) {
    stringstream ss(s);
    string item;
    vector<string> res;
    while (getline(ss, item, delim)) {
      res.emplace_back(item);
    }
    return res;
  }

private:
  unordered_map<string, Trie*> children;
  int fid = -1;
};

class Solution {
public:
  vector<string> removeSubfolders(vector<string>& folder) {
    Trie* trie = new Trie();
    for (int i = 0; i < folder.size(); ++i) {
      trie->insert(i, folder[i]);
    }
    vector<string> ans;
    for (int i : trie->search()) {
      ans.emplace_back(folder[i]);
    }
    return ans;
  }
};

type Trie struct {
  children map[string]*Trie
  isEnd  bool
}

func newTrie() *Trie {
  m := map[string]*Trie{}
  return &Trie{children: m}
}

func (this *Trie) insert(w string) {
  node := this
  for _, p := range strings.Split(w, "/")[1:] {
    if _, ok := node.children[p]; !ok {
      node.children[p] = newTrie()
    }
    node, _ = node.children[p]
  }
  node.isEnd = true
}

func (this *Trie) search(w string) bool {
  node := this
  for _, p := range strings.Split(w, "/")[1:] {
    if _, ok := node.children[p]; !ok {
      return false
    }
    node, _ = node.children[p]
    if node.isEnd {
      return true
    }
  }
  return false
}

func removeSubfolders(folder []string) []string {
  sort.Slice(folder, func(i, j int) bool {
    return len(strings.Split(folder[i], "/")) < len(strings.Split(folder[j], "/"))
  })
  trie := newTrie()
  var ans []string
  for _, v := range folder {
    if !trie.search(v) {
      trie.insert(v)
      ans = append(ans, v)
    }
  }
  return ans
}

Solution 3

type Trie struct {
  children map[string]*Trie
  fid    int
}

func newTrie() *Trie {
  return &Trie{map[string]*Trie{}, -1}
}

func (this *Trie) insert(fid int, f string) {
  node := this
  ps := strings.Split(f, "/")
  for _, p := range ps[1:] {
    if _, ok := node.children[p]; !ok {
      node.children[p] = newTrie()
    }
    node = node.children[p]
  }
  node.fid = fid
}

func (this *Trie) search() (ans []int) {
  var dfs func(*Trie)
  dfs = func(root *Trie) {
    if root.fid != -1 {
      ans = append(ans, root.fid)
      return
    }
    for _, child := range root.children {
      dfs(child)
    }
  }
  dfs(this)
  return
}

func removeSubfolders(folder []string) (ans []string) {
  trie := newTrie()
  for i, f := range folder {
    trie.insert(i, f)
  }
  for _, i := range trie.search() {
    ans = append(ans, folder[i])
  }
  return
}