LeetCode Longest Absolute File Path
Suppose we abstract our file system by a string in the following manner:
The string "dir\n\tsubdir1\n\tsubdir2\n\t\tfile.ext" represents:
dir
subdir1
subdir2
file.ext
The directory dir contains an empty sub-directory subdir1 and a sub-directory subdir2 containing a file file.ext.
The string "dir\n\tsubdir1\n\t\tfile1.ext\n\t\tsubsubdir1\n\tsubdir2\n\t\tsubsubdir2\n\t\t\tfile2.ext" represents:
dir
subdir1
file1.ext
subsubdir1
subdir2
subsubdir2
file2.ext
The directory dir contains two sub-directories subdir1 and subdir2. subdir1 contains a file file1.ext and an empty second-level sub-directory subsubdir1. subdir2contains a second-level sub-directory subsubdir2 containing a file file2.ext.
We are interested in finding the longest (number of characters) absolute path to a file within our file system. For example, in the second example above, the longest absolute path is "dir/subdir2/subsubdir2/file2.ext", and its length is 32 (not including the double quotes).
Given a string representing the file system in the above format, return the length of the longest absolute path to file in the abstracted file system. If there is no file in the system, return 0.
Note:
- The name of a file contains at least a
.and an extension. - The name of a directory or sub-directory will not contain a
..
O(n) where n is the size of the input string.
Notice that a/aa/aaa/file1.txt is not the longest file path, if there is another path aaaaaaaaaaaaaaaaaaaaa/sth.png.
给定一个文件系统的树形结构，要求以O(n)的复杂度找出最长路径的文件的路径长度，这里的长度包括分隔符’/’。 一开始我没有清晰的思路，后来在暗时间会拿出来思考，今天早上刷牙的时候想到了大概的解法。 遍历一次字符串，用一个vector保存当前看到的文件系统的最深层次，用level保存当前进入到的文件系统的深度。vector初始为空，level初始为0。每次我们找’\n’，因为’\n’表示一层文件系统的结束。每层文件系统level都从0开始。 比如第一个例子（如下），看到dir时，vector还是空的，所以vector.push_back(dir)。回车之后是’\t’，此时的level为0，且vector[0]有东西，说明要进入vector[0]表示的文件夹的下一层，level++。又遇到subdir1，此时的level=1了，已经大于等于vector的长度，说明目前进入到的深度已经超过了vector的表示范围，所以vector.push_back(subdir1)。 遇到’\n’又重新开始了，level为0。遇到’\t’，vector有，进入vector[0]，level++。遇到subdir2，此时level=1，但vector[1]有东西，此时需要把vector[1]覆盖为subdir2，因为目前看到的第1层已经是新的了。 遇到’\n’又重新开始，level为0。后面连遇到两个’\t’，且vector中都有对应，说明是在之前的路径里面，即dir/subdir2/。最后遇到file.ext文件，就能算到该文件的路径长度了。
dir
subdir1
subdir2
file.ext
代码如下。需要注意一点，如果一个string为”dir\n\tsubdir1\n\tsubdir2\n\t\tfile.ext”，里面的’\n’和’\t’虽然看起来是两个字符\加n或者t，但是实际是一个char为’\n’或’\t’，内存中只用一个字符char来表示，所以直接判断input[i]==’\n’即可。
[cpp]
class Solution {
public:
int lengthLongestPath(string input) {
vector<string> paths;
int maxLen = 0, n = input.size(), i = 0, j = 0;
while (j < n) {
bool isfile = false;
int curLen = 0, level = 0;
while (j < n&&input[j] != ‘\n’) {
if (input[j] == ‘.’)isfile = true;
else if (input[j] == ‘\t’) {
if (paths.size() <= level)paths.push_back(input.substr(i, j – i));
curLen += paths[level++].size() + 1; // +1指分隔符’/’
i = j + 1;
}
++j;
}
if (paths.size() <= level)paths.push_back(input.substr(i, j – i));
else paths[level] = input.substr(i, j – i);
curLen += paths[level++].size(); // 末尾不需要分隔符’/’
i = ++j;
if (isfile)maxLen = max(maxLen, curLen);
}
return maxLen;
}
};
[/cpp]
本代码提交AC，用时3MS。]]>