Question

1233. 删除子文件夹

English Version

题目描述

你是一位系统管理员，手里有一份文件夹列表 folder，你的任务是要删除该列表中的所有 子文件夹，并以 任意顺序 返回剩下的文件夹。

如果文件夹 folder[i] 位于另一个文件夹 folder[j] 下，那么 folder[i] 就是 folder[j] 的 子文件夹 。

文件夹的「路径」是由一个或多个按以下格式串联形成的字符串：'/' 后跟一个或者多个小写英文字母。

• 例如，"/leetcode" 和 "/leetcode/problems" 都是有效的路径，而空字符串和 "/" 不是。

 

示例 1：

输入：folder = ["/a","/a/b","/c/d","/c/d/e","/c/f"]
输出：["/a","/c/d","/c/f"]
解释："/a/b" 是 "/a" 的子文件夹，而 "/c/d/e" 是 "/c/d" 的子文件夹。

示例 2：

输入：folder = ["/a","/a/b/c","/a/b/d"]
输出：["/a"]
解释：文件夹 "/a/b/c" 和 "/a/b/d" 都会被删除，因为它们都是 "/a" 的子文件夹。

示例 3：

输入: folder = ["/a/b/c","/a/b/ca","/a/b/d"]
输出: ["/a/b/c","/a/b/ca","/a/b/d"]

 

提示：

• 1 <= folder.length <= 4 * 104
• 2 <= folder[i].length <= 100
• folder[i] 只包含小写字母和 '/'
• folder[i] 总是以字符 '/' 起始
• folder 每个元素都是 唯一 的

解法

方法一：排序

我们先将数组 folder 按照字典序排序，然后遍历数组，对于当前遍历到的文件夹 $f$，如果它的长度大于等于答案数组中最后一个文件夹的长度，并且它的前缀包含答案数组的最后一个文件夹再加上一个 /，则说明 $f$ 是答案数组中最后一个文件夹的子文件夹，我们不需要将其加入答案数组中。否则，我们将 $f$ 加入答案数组中。

遍历结束后，答案数组中的文件夹即为题目要求的答案。

时间复杂度 $O(n \times \log n \times m)$，空间复杂度 $O(m)$。其中 $n$ 和 $m$ 分别为数组 folder 的长度和数组 folder 中字符串的最大长度。

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
}

方法二：字典树

我们可以使用字典树存储数组 folder 中的所有文件夹。字典树的每个节点包含 children 字段，用于存储当前节点的子节点，以及 fid 字段，用于存储当前节点对应的文件夹在数组 folder 中的下标。

对于数组 folder 中的每个文件夹 $f$，我们先将 $f$ 按照 / 分割成若干个子串，然后从根节点开始，依次将子串加入字典树中。接下来，我们从根节点开始搜索字典树，如果当前节点的 fid 字段不为 -1，则说明当前节点对应的文件夹是答案数组中的一个文件夹，我们将其加入答案数组并且返回。否则，我们递归地搜索当前节点的所有子节点，最终返回答案数组。

时间复杂度 $O(n \times m)$，空间复杂度 $O(n \times m)$。其中 $n$ 和 $m$ 分别为数组 folder 的长度和数组 folder 中字符串的最大长度。

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
}

方法三

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
}