狗家 店面

没能找到利口类似的题，Google了一下有类似的，但感觉答案写得不对。求大佬们帮忙解答这题。感觉要用到graph和hashmap。。。

类似题：

原题：
Input is a list of String:
[
"/dir1/dir11/

您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

dir121
---file1.txt
-dir3
--file2.gif
-file3.html

别忘了加米！感谢！

trie + dfs可以解决掉吧

反着遍历list里的string，并用hashmap建一个n-ary tree。 最后pre-order traversal 这个树输出结果。 time complexity 是O（N） sapce complexity 也是 O（N）。N是dir / file 的个数

写出来了，就是建图+DFS，当然输出的顺序和上面不一样，但是结果是对的。 还请多多加米，多谢！
root = ""，root对应的都是一级folder和文件。

这题还是有容易出问题的地方，比如"file3.html",这里没有"/"所以直接是对应root

1. 
   
2. private static final String DASH = "-";
   
3.     public List<String> getAllDirectories(String[] input) {
   
4.         List<String> res = new ArrayList<>();
   
5.         if (input == null || input.length == 0) {
   
6.             return res;
   
7.         }
   
8.         Map<String, Set<String>> graph = new HashMap<>();
   
9.         buildGraph(input, graph);
   
10.         StringBuilder soluPrefix = new StringBuilder();
    
11.         getDirectories(res, graph, soluPrefix, "");
    
12.         return res;
    
13.     }
    
14. 
    
15.     private void buildGraph(String[] input, Map<String, Set<String>> graph) {
    
16.         graph.putIfAbsent("", new HashSet<>());
    
17.         for (String s: input) {
    
18.             String[] cur = s.split("/");
    
19.             if (cur.length == 1) {
    
20.                graph.get("").add(cur[0]);
    
21.             } else {
    
22.                 graph.get("").add(cur[1]);
    
23.             }
    
24.             for (int i = 1; i < cur.length; i++) {
    
25.                 graph.putIfAbsent(cur[i - 1], new HashSet<>());
    
26.                 graph.get(cur[i - 1]).add(cur[i]);
    
27.    [/i]         }
    
28.         }
    
29.     }
    
30. 
    
31.     private void getDirectories(List<String> res, Map<String, Set<String>> graph, StringBuilder soluPrefix, String cur) {
    
32.         if (graph.get(cur) == null) {
    
33.             return;
    
34.         }
    
35.         for (String next: graph.get(cur)) {
    
36.             int len = soluPrefix.length();
    
37.             soluPrefix.append(DASH).append(next);
    
38.             res.add(soluPrefix.toString());
    
39.             soluPrefix.setLength(len + 1);
    
40.             getDirectories(res, graph, soluPrefix, next);
    
41.             soluPrefix.setLength(len);
    
42.         }
    
43.     }
    

复制代码

只能想到暴力解法 string split成数组 用一个hashmap记录每个词出现的位置 如果后来出现比现在位置更靠后的替换掉 最后再输出。应该有更好的办法

补充内容 (2021-05-15 12:51 +8:00):
除了一个hashmap记录位置 还需要一个hashmap记录子目录 最后用dfs找出所有搭配

topological sort？每个url从前连到后然后bfs？

sort input 然后再用vector track 目前的directories ？

答案跟前面一样 创建一个node with multiple children。 不需要sort直接就开始塞。
赛完了dfs输出结果
时间复杂度就是O n

感觉要自己写个class吧

感觉是字典树

请问如果要用trie的话那单独一个file如“file3.html”需要单独处理还是insert到trie里呢？

还有是否要先sort input才能进行trie implementation？