388. 文件的最长绝对路径

1.题目

2.思路

通过观察可知，我们设字符串中第一个出现的目录的深度为0，那么’\t’的数目就是相应的文件或者文件夹所在的深度。例如示例2中dir深度为0，那么subdir的深度为1，其前面的’\t’的数目也为1。这样我们可以统计’\t’的数目知道紧跟在后面的文件或文件夹所在的层次。设’\t’的数目为depth即为当前文件或文件夹的深度。同时我们可以使用栈来记录上一次的遍历到的结果，例如示例2中假设已经遍历到file1.txt，我们记录这时的路径长度，并将其放入栈中。栈中最底层元素对应当前路径的一个分层的字符串长度，例如遍历到file1.txt，栈中的元素分别为dir的长度、dir/subdir的长度，遍历到file1.txt后压入栈的元素长度为栈顶元素即dir/subdir的长度+1+file1.txt的长度。当前深度如果小于栈内元素时，说明需要返回到当前深度的前一层次并再将当前深度的元素压入栈中，返回当当前深度的上一层次，只需不断弹出栈内元素直到当前深度与栈的大小相等。同时考虑到求解的文件的最长绝对路径，那么我们需要判断是否当前遍历到的是文件还是文件夹，如果为文件则需要用当前结果更新最终的最长绝对路径。

3.代码

class Solution {
public:
    int lengthLongestPath(string input) {
        int ans = 0, n = input.size();
        if(input.find(".") == input.npos)
            return ans;
        stack<int> s;
        for(int i = 0; i < n;)
        {
            bool isFile = false;
            int  depth = 0;
            while(i < n && input[i] == '\t')
            {
                depth++;
                i++;
            }
            int l = 0;
            while(input[i] != '\n' && i < n)
            {
                if(input[i] == '.')
                    isFile = true;
                l++;
                i++;
            }
            i++;
            while(depth < s.size())
            {
                s.pop();
            }
            if(!s.empty())
                l += s.top()+1;
            if(isFile)
            {
                ans = max(ans, l);
            }
            else
            {
                s.emplace(l);
            }
        }
        return ans;    
    }
};