388. Longest Absolute File Path -----M ~~~

 Suppose we have the file system represented in the following picture:

We will represent the file system as a string where "\n\t" mean a subdirectory of the main directory, "\n\t\t" means a subdirectory of the subdirectory of the main directory and so on. Each folder will be represented as a string of letters and/or digits. Each file will be in the form "s1.s2" where s1 and s2 are strings of letters and/or digits.

For example, the file system above is represented as "dir\n\tsubdir1\n\t\tfile1.ext\n\t\tsubsubdir1\n\tsubdir2\n\t\tsubsubdir2\n\t\t\tfile2.ext".

Given a string input representing the file system in the explained format, return the length of the longest absolute path to a file in the abstracted file system. If there is no file in the system, return 0.

 

Example 1:

Input: input = "dir\n\tsubdir1\n\tsubdir2\n\t\tfile.ext"
Output: 20
Explanation: We have only one file and its path is "dir/subdir2/file.ext" of length 20.
The path "dir/subdir1" doesn't contain any files.

Example 2:

Input: input = "dir\n\tsubdir1\n\t\tfile1.ext\n\t\tsubsubdir1\n\tsubdir2\n\t\tsubsubdir2\n\t\t\tfile2.ext"
Output: 32
Explanation: We have two files:
"dir/subdir1/file1.ext" of length 21
"dir/subdir2/subsubdir2/file2.ext" of length 32.
We return 32 since it is the longest path.

Example 3:

Input: input = "a"
Output: 0
Explanation: We don't have any files.

 

Constraints:

• 1 <= input.length <= 104
• input may contain lower-case or upper-case English letters, a new line character '\n', a tab character '\t', a dot '.', a space ' ' or digits.

A:

其实并不难。 就是一层层转化。

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39

class Solution { public: int lengthLongestPath(string input) { vector<string> lines; stringstream checker(input); string tmp; while(getline(checker, tmp, '\n')){ lines.push_back(tmp); } return helper(lines); } private: int helper(vector<string> lines){ int n = lines.size(); if(n== 0) return 0; // do not found anything, return false int start = 0; int res = 0; while(start<n){ string root = lines[start]; // root folder of the lines if(root.find(".") != string::npos){ res = max(res, int(root.length())); start++; }else{// root is the parent folder, we need to find rest subdir start++; // go to next line vector<string> newLines; while(start<n && lines[start][0] == '\t'){ newLines.push_back(lines[start].substr(1)); start++; } int childLen = helper(newLines); if(childLen >0){ res = max(res, int(root.length())+1 + childLen);// +1 for "/" } } } return res; } };

错误在：

一开始想用结果  -1  来代表没有值。 然而是不对的。应该是0 

Line 28, 忘记了取substr(1) ,来去掉开头的 "\t"

Learned：

1： how to tokenize String

2:   string find operation and result