LeetCode 388. 文件的最长绝对路径

题目链接：文件的最长绝对路径

题解标签：哈希表、前缀和

思路：

        1）文件要么是字符串尾部，要么后面跟着 n

        2）文件或文件夹所在层级为上一个 n 后 t 的个数

        3）文件路径长度为上层文件夹路径长度+文件名长度

        只需要维护一个hash表（数组也可），记录每个层级的文件夹或文件名长度即可。

        e.g.

        字符串从前往后遍历

                ①遇到 t ，层级+1

                ②遇到 n ，尝试更新答案，层级置零

                ③其他，当前文件夹或文件名长度+1

代码：leetcode/ProblemThree88LongestAbsoluteFilePath.java at master · 1025100302/leetcode (github.com)

class Solution {
        public int lengthLongestPath(String input) {
            input = input + 'n';
            int ans = 0;
            // 记录每一层的长度
            Map recordMap = new HashMap<>();
            int len = input.length();
            // level表示文件层级，curLen表示当前文件夹名或文件名的长度
            int level = 0, curLen = 0;
            boolean isFile = false;
            for (int i = 0; i < len; i++) {
                char c = input.charAt(i);
                if (c != 'n' && c != 't') {
                    curLen++;
                    if (c == '.') isFile = true;
                } else {
                    // 当前层级的长度等于上一层的长度+1（连接符：/）
                    if (curLen > 0) recordMap.put(level, recordMap.getOrDefault(level - 1, 0) + curLen + 1);
                    if (input.charAt(i) == 'n') {
                        // 只记录文件的路径长度，忽略文件夹的路径长度
                        if (isFile) ans = Math.max(ans, recordMap.get(level));
                        level = 0;
                    } else {
                        level++;
                    }
                    curLen = 0;
                    isFile = false;
                }
            }
            return Math.max(0, ans - 1);
        }
    }

运行结果：
            执行耗时:1 ms,击败了65.17% 的Java用户
            内存消耗:39.4 MB,击败了34.42% 的Java用户