Longest Absolute File Path结题报告

Link:

https://leetcode.com/problems/longest-absolute-file-path/description/

解题方法：

当读到一个子目录或者一个文件时，要记录当前的长度，必然要知道这个上一级的长度。
而根据题意可知，给出的字符串实际是将一个目录树先序遍历产生的。也就是说如果我们用一个哈希（代表level 到 这个level的长度的映射）来记录每层的长度，当需要计算当前层数的长度时，只需要找hash[level - 1]即可，因为当我们要计算hash[level]时候，hash[level-1]一定会在之前被更新为对应的上一层长度。

Mistake:

最后不要忘记把路劲中的'/'算进去。

Time Complexity：

O(N)

完整代码：

int lengthLongestPath(string input) 
    {
        int maxLen = 0;
        int currLevel = 0;
        unordered_map <int, int> hash;
        hash[-1] = 0;
        string curr;
        bool isFile = false;
        for(int i = 0; i <= input.size(); i++)
        {
            if(input[i] == '\n' || i == input.size())
            {
                int currLen = curr.size() + hash[currLevel - 1] + 1;
                curr.clear();
                hash[currLevel] = currLen;
                currLevel = 0;
                if(isFile)
                    maxLen = currLen > maxLen ? currLen : maxLen;
                isFile = false;
            }
            else
            {
                if(input[i] == '\t')
                {
                    currLevel++;
                    continue;
                }
                if(input[i] == '.')
                    isFile = true;
                curr += input[i];
            }
        }
        return maxLen > 0 ? maxLen - 1 : 0;
    }