LeetCode 文件的最长绝对路径

假设我们以下述方式将我们的文件系统抽象成一个字符串:

字符串 "dir\n\tsubdir1\n\tsubdir2\n\t\tfile.ext" 表示:

dir
    subdir1
    subdir2
        file.ext
目录 dir 包含一个空的子目录 subdir1 和一个包含一个文件 file.ext 的子目录 subdir2 。

字符串 "dir\n\tsubdir1\n\t\tfile1.ext\n\t\tsubsubdir1\n\tsubdir2\n\t\tsubsubdir2\n\t\t\tfile2.ext" 表示:

dir
    subdir1
        file1.ext
        subsubdir1
    subdir2
        subsubdir2
            file2.ext
目录 dir 包含两个子目录 subdir1 和 subdir2。 subdir1 包含一个文件 file1.ext 和一个空的二级子目录 subsubdir1。subdir2 包含一个二级子目录 subsubdir2 ，其中包含一个文件 file2.ext。

我们致力于寻找我们文件系统中文件的最长 (按字符的数量统计) 绝对路径。例如，在上述的第二个例子中，最长路径为 "dir/subdir2/subsubdir2/file2.ext"，其长度为 32 (不包含双引号)。

给定一个以上述格式表示文件系统的字符串，返回文件系统中文件的最长绝对路径的长度。 如果系统中没有文件，返回 0。

说明:

文件名至少存在一个 . 和一个扩展名。
目录或者子目录的名字不能包含 .。
要求时间复杂度为 O(n) ，其中 n 是输入字符串的大小。
请注意，如果存在路径 aaaaaaaaaaaaaaaaaaaaa/sth.png 的话，那么  a/aa/aaa/file1.txt 就不是一个最长的路径。

思路分析：这道题不难，但是具体的细节需要很严密的逻辑。

假设给你“path.txt”，返回的结果应该是8，"path.txt"就是绝对路径
假设给你“path\n\tfile”，返回的结果应该是0，因为不存在文件名，都是文件夹的名
假设给你“path\n\tfile.txt”，返回的结果应该是13，最长绝对路径是"path/file.txt",注意中间需要添加额外的斜杠
假设给你“\npath\n\tfile.txt”，返回的结果应该是13，最长绝对路径是"path/file.txt",最前面的“\n”不影响
假设给你“path\n    file.txt”，返回的结果应该是13，最长绝对路径是"path/file.txt",注意中间有四个空格可代替一个‘\t’（题目测试示例非常贱！！！）
假设给你“path\n\t    file.txt”，返回的结果应该是17，最长绝对路径是"path/    file.txt",中间虽有四个空格但是之前有的'\t'已经可以表达file.txt是path目录的子文件\夹，所以这四个空格只能看作为file.txt文件的文件名（题目测试示例非常贱！！！）

具体实现代码：

class Solution {
public:
    int result;
    //nowIndex是指正在访问的下标，beforeLength上一层目录的长度，beforeFloor上一层n目录的'\t'个数
    int dfs(string &input, int nowIndex, int beforeLength, int beforeFloor){
        int inputSize = (int)input.size();
        while (nowIndex < inputSize){
            //判断第一个字符是否是'\n'
            if (input[nowIndex] == '\n'){
                nowIndex += 1;//跳过“\n"
                //计算当前的层数'\t'的个数，只有当'\t'的数比上一层目录'\t'的个数多1，才能说明下面的文件是上一层的子目录
                int tempFloor = 0;
                while (input[nowIndex] == '\t' || input[nowIndex] == ' '){
                    tempFloor += 1;
                    //四个空格也是一个table键
                    if (input[nowIndex] == ' '){
                        nowIndex += 3;
                    }
                    nowIndex += 1;
                    //如果已经计算到的'\t‘能够表达是上一层目录的子目录，停止计算'\t’，解决“path\n\t    file.txt”这种空格算文件名的问题
                    if (tempFloor == beforeFloor + 1){
                        break;
                    }
                }
                if (tempFloor == 0){
                    //如果计算到'\t'的个数为零，说明这是一个根目录，beforeLength，beforeFloor清零
                    nowIndex = dfs(input, nowIndex, 0, 0);
                }
                else if (tempFloor <= beforeFloor){
                    //如果当前层数小于之前的层数，说明不是上一层的子目录，返回并回退已计算了的‘\n'和'\t'
                    return nowIndex - tempFloor - 1;
                }
                else{
                    //否则说明这是上一个目录的子目录
                    //读取下一个文件名
                    bool isFile = false;//是否是文件
                    string tempStr = "";
                    while (nowIndex < inputSize && input[nowIndex] != '\n'){
                        tempStr += input[nowIndex];
                        if (input[nowIndex++] == '.'){//出现扩展名，说明是文件
                            isFile = true;
                        }
                    }
                    if (isFile){
                        //是文件名，此层访问结束
                        result = max(result, int(beforeLength + 1 + tempStr.size()));
                    }
                    else{
                        //不是文件继续递归访问
                        nowIndex = dfs(input, nowIndex, int(beforeLength + 1 + tempStr.size()), beforeFloor + 1);
                    }
                }
            }
            else{
                //第一个字符不是'\n'说明这是根目录
                //读取下一个文件名
                bool isFile = false;//是否是文件
                string tempStr = "";
                while (nowIndex < inputSize && input[nowIndex] != '\n'){
                    tempStr += input[nowIndex];
                    if (input[nowIndex++] == '.'){//出现扩展名，说明是文件
                        isFile = true;
                    }
                }
                if (isFile){
                    //是文件名，此层访问结束
                    result = max(result, int(beforeLength + tempStr.size()));
                }
                else{
                    //不是文件继续递归访问
                    nowIndex = dfs(input, nowIndex, int(tempStr.size()), 0);
                }
            }
        }
        return nowIndex;
    }
    
    int lengthLongestPath(string input) {
        result = 0;
        dfs(input, 0, 0, 0);//从零开始搜索
        return result;
    }
};

LeetCode 文件的最长绝对路径
这题目的测试数据太贱了。。。

LeetCode 文件的最长绝对路径

相关推荐