删除子文件夹【LC1233】
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.
连续的雨天
排序+双指针
- 思路：
将字符串按照字典顺序排序，将所有位于一个根目录下的文件夹视为一组，使用滑动窗口找到所有的根目录，放入结果集。
实现
排序后，左指针指向的目录为根目录，如果右指针对应的目录包含根目录+'/'，那么证明它们位于一个根目录下
class Solution { public List<String> removeSubfolders(String[] folder) { Arrays.sort(folder); List<String> res = new ArrayList<>(); int l = 0, n = folder.length; while (l < n){ int lenL = folder[l].length(); int r = l; while(r + 1 < n && folder[r + 1].length() > lenL && folder[r + 1].substring(0,lenL).equals(folder[l]) && folder[r + 1].charAt(lenL) == '/'){ r++; } res.add(folder[l]); l = r + 1; } return res; } }
复杂度
时间复杂度：O ( n l o g n )
空间复杂度：O ( 1
排序+去重
- 实现：换一种写法，枚举判断每一个目录是否位于前一个根目录下，如果是，那么跳过这个目录；如果不是，那么这个目录为新的根目录，放入结果中
class Solution { public List<String> removeSubfolders(String[] folder) { Arrays.sort(folder); List<String> res = new ArrayList<>(); int l = 0, n = folder.length; while (l < n){ int lenL = folder[l].length(); int r = l; while(r + 1 < n && folder[r + 1].length() > lenL && folder[r + 1].substring(0,lenL).equals(folder[l]) && folder[r + 1].charAt(lenL) == '/'){ r++; } res.add(folder[l]); l = r + 1; } return res; } }
复杂度
时间复杂度：O ( n ∗ l ∗ l o g n )， n 是数组的长度，l 是文件夹的平均长度，排序所需要的时间复杂度为O ( n ∗ l ∗ l o g n )
空间复杂度：O ( l ) ，截取子串需要的空间
字典树：全部加入再判断
- 思路：
使用字典树存储所有的目录，并使用属性isEnd记录是否是一个目录的末尾。然后对于每一个目录判断其所有前缀是否是根目录（前缀的末尾isEnd属性是true，并且下一个字符串是’/'）。如果是，那么该目录是子目录，跳过；如果不是，那么该目录是根目录，加入结果集
- 实现
- 字典树
- 可能包含27个字符：26个小写字母+‘/’
- insert：将所有字符串加入字典树中
- search：搜索每个字符串的前缀字符串是否是根目录，是，则返回true；否，返回false，加入结果集。
class Solution { class Tire{ class TireNode{ TireNode[] next = new TireNode[27]; boolean isEnd; } TireNode root; public Tire(){ root = new TireNode(); } public void insert(String s){ TireNode p = root; for (char c : s.toCharArray()){ int u = c == '/' ? 26 : c - 'a'; if (p.next[u] == null) p.next[u] = new TireNode(); p = p.next[u]; } p.isEnd = true; } public boolean search(String s){ TireNode p = root; for (char c : s.toCharArray()){ if (p.isEnd && c == '/' ) return true;// 是根目录 int u = c == '/' ? 26 : c - 'a'; p = p.next[u]; } return false;// 不是根目录 } } public List<String> removeSubfolders(String[] folder) { List<String> res = new ArrayList<>(); Tire tire = new Tire(); for (String s : folder){ tire.insert(s);// 加入字典树 } for (String s : folder){ if (!tire.search(s)){// 判断前缀字符串是否是根目录 res.add(s); } } return res; } }
复杂度
时间复杂度：O ( n ∗ l ) ，n 是数组的长度，l 是文件夹的平均长度
空间复杂度：O ( n ∗ l )
字典树：边加入边判断
- 思路：边加入边判断
将数组进行排序，保证根目录一定出现在子目录之前，边加入目录，一边判断目录是否包含之前的根目录，在insert中直接返回true或者false - 实现
class Solution { class Tire{ class TireNode{ TireNode[] next = new TireNode[27]; boolean isEnd; } TireNode root; public Tire(){ root = new TireNode(); } public boolean insert(String s){ TireNode p = root; for (char c : s.toCharArray()){ if (p.isEnd && c == '/') return false;// 子目录 add不成功 int u = c == '/' ? 26 : c - 'a'; if (p.next[u] == null) p.next[u] = new TireNode(); p = p.next[u]; } p.isEnd = true; return true; // 新的根目录 add成功 } } public List<String> removeSubfolders(String[] folder) { Arrays.sort(folder); List<String> res = new ArrayList<>(); Tire tire = new Tire(); for (String s : folder){ if(tire.insert(s)){ res.add(s); } } return res; } }
复杂度
时间复杂度：O ( n ∗ l ∗ l o g n ) ，n是数组的长度，l 是文件夹的平均长度，排序所需要的时间复杂度为O ( n ∗ l ∗ l o g n ) ，insert所需要的时间复杂度为O ( n ∗ l )
空间复杂度：O ( n ∗ l )
