狗家 店面

自己写的，作为参考，不知道这个思路对不对

1. class Solution:
   
2.     # one pass, O(n) time
   
3.     # really don't need to store all paths since we only return max length
   
4.     def longestPath(self, s: str) -> int:
   
5.         entries = s.split('\n')
   
6.         # stack to track parent dir and level, root level is -1
   
7.         stack = [(-1, '')]
   
8.         # paths for all entries
   
9.         paths = []
   
10.         maxLen = -1
    
11.         for e in entries:
    
12.             level = self.countLevel(e)
    
13.             parent_level, parent_dir = stack[-1]
    
14.             # trim spaces
    
15.             e = e.strip()
    
16.             # popping until correct parent dir is found
    
17.             while level <= parent_level:
    
18.                 stack.pop()
    
19.                 parent_level, parent_dir = stack[-1]
    
20. 
    
21.             path = parent_dir + '/' + e
    
22.             paths.append(path)
    
23.             # dir
    
24.             if self.isDir(e):
    
25.                 stack.append((level, path))
    
26.             # image file
    
27.             elif self.isImageFile(e):
    
28.                 # update max path length for image files
    
29.                 maxLen = max(maxLen, len(path))
    
30. 
    
31.         return maxLen
    
32. 
    
33.     def countLevel(self, s):
    
34.         space = 0
    
35.         for c in s:
    
36.             if c == ' ':
    
37.                 space += 1
    
38.             else:
    
39.                 break
    
40.         return space
    
41. 
    
42.     def isDir(self, s):
    
43.         return '.' not in s
    
44. 
    
45.     def isImageFile(self, s):
    
46.         return '.jpeg' in s or '.png' in s or '.gif' in s
    
47. 
    
48. 
    
49. filestr = '''dir1
    
50. dir11
    
51. dir12
    
52.   picture.jpeg
    
53.   dir121
    
54. file1.txt
    
55. dir2
    
56. verylongfilename2.gif'''
    
57. s = Solution()
    
58. a = s.longestPath(filestr)
    
59. # '/dir2/verylongfilename2.gif' = 27
    
60. print(a)
    

复制代码

感觉是deserialize string back to data structure。这个题因为是返回最大值，所以应该用不到tree或者dfs, 每一行算下最大值（图片文件）

匿名者 发表于 2021-5-15 13:45
反着遍历list里的string，并用hashmap建一个n-ary tree。 最后pre-order traversal 这个树输出结果。 time  ...

请问为什么要反着遍历list里的string？ 能具体说一下吗？

ND0406 发表于 2021-5-15 15:15
答案跟前面一样 创建一个node with multiple children。 不需要sort直接就开始塞。
赛完了dfs输出结果
时间 ...

我感觉也是这样，直接用HashMap创建一个一对多的图，然后DFS遍历图即可

写出来了，就是建图+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.     }
    

复制代码

BFS，注意的是这里只用了一个StringBuilder，所以在BFS时先加上“-”，然后再加下一个节点，放入结果后要删除刚添加的节点方便下一个节点用。
比如 -dir1已经加入到结果种，要删除dir1，还原StringBuilder，所以下一个就是"-dir3"了

1. 
   
2. public List<String> getAllDirectoriesBFS(String[] input) {
   
3.    List<String> res = new ArrayList<>();
   
4.    if (input == null || input.length == 0) {
   
5.       return res;
   
6.    }
   
7.    Map<String, Set<String>> graph = new HashMap<>();
   
8.    buildGraph(input, graph);
   
9.    getDirectoriesBFS(res, graph);
   
10.    return res;
    
11. }
    
12. 
    
13. private void buildGraph(String[] input, Map<String, Set<String>> graph) {
    
14.    graph.putIfAbsent("", new HashSet<>());
    
15.    for (String s: input) {
    
16.       String[] cur = s.split("/");
    
17.       if (cur.length == 1) {
    
18.           graph.get("").add(cur[0]);
    
19.       } else {
    
20.          graph.get("").add(cur[1]);
    
21.       }
    
22.       for (int i = 1; i < cur.length; i++) {
    
23.          graph.putIfAbsent(cur[i - 1], new HashSet<>());
    
24.          graph.get(cur[i - 1]).add(cur[i]);
    
25.       }
    
26.    }
    
27. }
    
28. 
    
29. private void getDirectoriesBFS(List<String> res, Map<String, Set<String>> graph) {
    
30.    StringBuilder soluPrefix = new StringBuilder();
    
31.    Queue<String> queue = new ArrayDeque<>();
    
32.    queue.offer("");
    
33.    while (!queue.isEmpty()) {
    
34.       int size = queue.size();
    
35.       soluPrefix.append(DASH);
    
36.       for (int i = 0; i < size; i++) {
    
37.          String cur = queue.poll();
    
38.          Set<String> nextSet = graph.get(cur);
    
39.          if (nextSet == null) {
    
40.             continue;
    
41.          }
    
42.          int len = soluPrefix.length();
    
43.          for (String next : nextSet) {
    
44.             soluPrefix.append(next);
    
45.             res.add(soluPrefix.toString());
    
46.             soluPrefix.setLength(len);
    
47.             queue.offer(next);
    
48.          }
    
49.       }
    
50.    }
    
51. }
    

复制代码

昨天想想就感觉不对，这个明显用DFS/BFS是杀鸡用牛刀了，其实Stack就可以了，StringBuilder作为stack就可以了，只不过如果想要输出那种格式还需要一开始就同时用一个Set和List

1. private static final String DASH = "-";
   
2. public Set<String> getAllDirectoriesSimple(String[] input) {
   
3.         Set<String> res = new HashSet<>();
   
4.         if (input == null || input.length == 0) {
   
5.             return res;
   
6.         }
   
7.         StringBuilder sb = new StringBuilder();
   
8.         sb.append(DASH);
   
9.         int depth = 1;
   
10.         for (String s: input) {
    
11.             if (s.charAt(0) == '/') {
    
12.                 for (int i = 1; i < s.length(); i++) {
    
13.                     char c = s.charAt(i);
    
14.                     if (c == '/') {
    
15.                         res.add(sb.toString());
    
16.                         sb.setLength(count);
    
17.                         depth++;
    
18.                         sb.append(DASH);
    
19.                     } else {
    
20.                         sb.append(c);
    
21.                     }
    
22.                 }
    
23.                 res.add(sb.toString());
    
24.                 depth = 1;
    
25.             } else {
    
26.                 sb.append(s);
    
27.                 res.add(sb.toString());
    
28.             }
    
29.             sb.setLength(1);
    
30.         }
    
31.         return res;
    
32.     }
    

复制代码

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

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

感觉一个一个扫描还是太麻烦了，直接split转成array吧，但是感觉狗家就喜欢考Trie和DP，是不是应该用Trie做啊
注意，split之后 所有”/”开始的第一个元素都是空的

1. private static final String DASH = "-";
   
2. public List<String> getAllDirectoriesSimple2(String[] input) {
   
3.    List<String> res = new ArrayList<>();
   
4.    Set<String> dict = new HashSet<>();
   
5.    if (input == null || input.length == 0) {
   
6.       return res;
   
7.    }
   
8.    StringBuilder sb = new StringBuilder();
   
9.    int depth = 0;
   
10.    for (String s: input) {
    
11.       String[] curFolders = s.split("/");
    
12.       for (String curFolder: curFolders)  {
    
13.          if (curFolder.isEmpty()) {
    
14.             continue;
    
15.          }
    
16.          sb.append(DASH);
    
17.          sb.append(curFolder);
    
18.          depth++;
    
19.          if (dict.add(sb.toString())) {
    
20.             res.add(sb.toString());
    
21.          }
    
22.          sb.setLength(depth);
    
23.       }
    
24.       sb.setLength(0);
    
25.       depth = 0;
    
26.    }
    
27.    return res;
    
28. }
    

复制代码

如果想省时间，那可以每次都建一个StringBuilder，

1. private static final String DASH = "-";
   
2. public List<String> getAllDirectoriesSimple2(String[] input) {
   
3.         List<String> res = new ArrayList<>();
   
4.         Set<String> dict = new HashSet<>();
   
5.         if (input == null || input.length == 0) {
   
6.             return res;
   
7.         }
   
8.         int depth = 0;
   
9.         for (String s: input) {
   
10.             String[] curFolders = s.split("/");
    
11.             for (String curFolder: curFolders)  {
    
12.                 if (curFolder.isEmpty()) {
    
13.                     continue;
    
14.                 }
    
15.                 StringBuilder sb = new StringBuilder();
    
16.                 depth++;
    
17.                 for (int i = 0; i < depth; i++) {
    
18.                     sb.append(DASH);
    
19.                 }
    
20.                 sb.append(curFolder);
    
21.                 if (dict.add(sb.toString())) {
    
22.                     res.add(sb.toString());
    
23.                 }
    
24.             }
    
25.             depth = 0;
    
26.         }
    
27.         return res;
    
28.     }
    

复制代码