leetcode 388. Longest Absolute File Path | 388. 文件的最长绝对路径（栈+DFS）

我就是我 2022-08-31 15:17 132阅读 0赞

## 题目 ##

[https://leetcode.com/problems/longest-absolute-file-path/][https_leetcode.com_problems_longest-absolute-file-path]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzQyNDgzMzQx_size_16_color_FFFFFF_t_70]

## 题解 ##

![在这里插入图片描述][58ab7bc7dd11476aacb9bebc21d57a6b.png]  
没有思路的时候，看 Related Topics，知道这题在考察什么了，顺着这个方向想就好了。

顺便贴一下草稿：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzQyNDgzMzQx_size_1_color_FFFFFF_t_70]

class Solution { 
        public int lengthLongestPath(String input) { 
            String[] list = input.split("\\n");
            Stack<Integer> stack = new Stack<>(); // 栈中记录累计长度
            int maxLen = 0;
            for (String s : list) { 
                int d = getDepth(s); // 获取当前目录的depth
                while (d < stack.size()) {  // 不断出栈，直到当前目录被可以包含在栈顶元素中
                    stack.pop();
                }
                if (s.contains(".")) {  // file
                    maxLen = Math.max((stack.isEmpty() ? -1 : stack.peek()) + s.length() - d + 1, maxLen); // -1是由于根目录没有前导/，+1是计算包含前导/的长度
                } else {  // dir
                    stack.push((stack.isEmpty() ? -1 : stack.peek()) + s.length() - d + 1);
                }
            }
            return maxLen;
        }
    
        public int getDepth(String s) { 
            int d = 0;
            while (s.startsWith("\t")) { 
                d++;
                s = s.substring(1);
            }
            return d;
        }
    }

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzQyNDgzMzQx_size_16_color_FFFFFF_t_70 1]

[https_leetcode.com_problems_longest-absolute-file-path]: https://leetcode.com/problems/longest-absolute-file-path/
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzQyNDgzMzQx_size_16_color_FFFFFF_t_70]: /images/20220829/eb817a256dfe425eb620bdaa0dce95a3.png
[58ab7bc7dd11476aacb9bebc21d57a6b.png]: /images/20220829/8b3f70332a68460b81d891d638379186.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzQyNDgzMzQx_size_1_color_FFFFFF_t_70]: /images/20220829/8d8d64a1fdb94455bd45abe4a7446866.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzQyNDgzMzQx_size_16_color_FFFFFF_t_70 1]: /images/20220829/d32ef0ab50ea41d9ba25a9cb492e8fe9.png