Welcome to Subscribe On Youtube
Question
Formatted question description: https://leetcode.ca/all/388.html
Suppose we have a file system that stores both files and directories. An example of one system is represented in the following picture:
Here, we have dir
as the only directory in the root. dir
contains two subdirectories, subdir1
and subdir2
. subdir1
contains a file file1.ext
and subdirectory subsubdir1
. subdir2
contains a subdirectory subsubdir2
, which contains a file file2.ext
.
In text form, it looks like this (with ⟶ representing the tab character):
dir ⟶ subdir1 ⟶ ⟶ file1.ext ⟶ ⟶ subsubdir1 ⟶ subdir2 ⟶ ⟶ subsubdir2 ⟶ ⟶ ⟶ file2.ext
If we were to write this representation in code, it will look like this: "dir\n\tsubdir1\n\t\tfile1.ext\n\t\tsubsubdir1\n\tsubdir2\n\t\tsubsubdir2\n\t\t\tfile2.ext"
. Note that the '\n'
and '\t'
are the new-line and tab characters.
Every file and directory has a unique absolute path in the file system, which is the order of directories that must be opened to reach the file/directory itself, all concatenated by '/'s
. Using the above example, the absolute path to file2.ext
is "dir/subdir2/subsubdir2/file2.ext"
. Each directory name consists of letters, digits, and/or spaces. Each file name is of the form name.extension
, where name
and extension
consist of letters, digits, and/or spaces.
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
.
Note that the testcases are generated such that the file system is valid and no file or directory name has length 0.
Example 1:
Input: input = "dir\n\tsubdir1\n\tsubdir2\n\t\tfile.ext" Output: 20 Explanation: We have only one file, and the absolute path is "dir/subdir2/file.ext" of length 20.
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 absolute path to a file.
Example 3:
Input: input = "a" Output: 0 Explanation: We do not have any files, just a single directory named "a".
Constraints:
1 <= input.length <= 104
input
may contain lowercase or uppercase English letters, a new line character'\n'
, a tab character'\t'
, a dot'.'
, a space' '
, and digits.- All file and directory names have positive length.
Algorithm
For each line, we find the position of the last space character \t
, and then we can get the name of the file or folder, and then we judge whether it is a file or a folder, if it is a file, update res, if it is a folder, update HashMap mapping.
Code
-
import java.util.HashMap; import java.util.Map; public class Longest_Absolute_File_Path { public static void main (String[] a) { Longest_Absolute_File_Path out = new Longest_Absolute_File_Path(); Solution s = out.new Solution(); //@note: System.out.println("abcdef".lastIndexOf("cd")); // output: 2 String input = "dir\n\tsubdir1\n\t\tfile1.ext\n\t\tsubsubdir1\n\tsubdir2\n\t\tsubsubdir2\n\t\t\tfile2.ext"; System.out.println(s.lengthLongestPath(input)); // output: 32 } public class Solution { public int lengthLongestPath(String input) { int res = 0; // HashMap 深度 level => 当前深度的绝对路径长度 all prev path length Map<Integer, Integer> m = new HashMap<>(); m.put(0, 0); String[] lines = input.split("\n"); for (String s : lines) { // @note: s="\tsubdir1" // s.charAt(0) = "\t" // s.indexOf("\t") = 0 // s.lastIndexOf("\t") = 0 int level = s.lastIndexOf("\t") + 1; int len = s.substring(level).length(); if (s.contains(".")) { res = Math.max(res, m.get(level) + len); // no +1, no `/` } else { m.put(level + 1, m.get(level) + len + 1); // evertime a new sublevel, prev will be overwritten } } return res; } } } ############ class Solution { public int lengthLongestPath(String input) { int i = 0; int n = input.length(); int ans = 0; Deque<Integer> stack = new ArrayDeque<>(); while (i < n) { int ident = 0; for (; input.charAt(i) == '\t'; i++) { ident++; } int cur = 0; boolean isFile = false; for (; i < n && input.charAt(i) != '\n'; i++) { cur++; if (input.charAt(i) == '.') { isFile = true; } } i++; // popd while (!stack.isEmpty() && stack.size() > ident) { stack.pop(); } if (stack.size() > 0) { cur += stack.peek() + 1; } // pushd if (!isFile) { stack.push(cur); continue; } ans = Math.max(ans, cur); } return ans; } }
-
// OJ: https://leetcode.com/problems/longest-absolute-file-path/ // Time: O(N) // Space: O(N) class Solution { public: int lengthLongestPath(string input) { stack<int> len; stringstream ss(input); string line; int ans = 0; while (getline(ss, line)) { int lv = 0; while (lv < line.size() && line[lv] == '\t') ++lv; while (len.size() > lv) len.pop(); int pathLen = len.empty() ? 0 : len.top(), curLen = line.size() - lv; if (line.find('.') != string::npos) { ans = max(ans, pathLen + curLen); } else { len.push(pathLen + 1 + curLen); } } return ans; } };
-
class Solution: def lengthLongestPath(self, input: str) -> int: i, n = 0, len(input) ans = 0 stk = [] while i < n: ident = 0 while input[i] == '\t': ident += 1 i += 1 cur, isFile = 0, False while i < n and input[i] != '\n': cur += 1 if input[i] == '.': isFile = True i += 1 i += 1 # popd while len(stk) > 0 and len(stk) > ident: stk.pop() if len(stk) > 0: cur += stk[-1] + 1 # pushd if not isFile: stk.append(cur) continue ans = max(ans, cur) return ans ############ class Solution(object): def lengthLongestPath(self, input): """ :type input: str :rtype: int """ maxLen = 0 curLen = 0 stack = [] dfa = {"init": 0, "char": 1, "escapeCMD": 2, "file": 3} state = 0 start = 0 level = 0 for i in range(0, len(input)): chr = input[i] if chr == '\n': curLen = 0 if len(stack) == 0 else stack[-1][1] if state == dfa["char"]: curLen += i - start stack.append((input[start:i], curLen + 1, level)) elif state == dfa["file"]: maxLen = max(maxLen, curLen + (i - start)) else: return -1 state = dfa["escapeCMD"] level = 0 elif chr == '\t': if state == dfa["escapeCMD"]: level += 1 else: return "TAB cannot be here" elif chr == '.': if state == dfa["char"] or state == dfa["file"] or state == dfa["escapeCMD"]: state = dfa["file"] else: return "unexpected char before dot", state else: if state == dfa["escapeCMD"]: while stack and stack[-1][2] >= level: stack.pop() start = i state = dfa["char"] elif state == dfa["init"]: state = dfa["char"] elif i == len(input) - 1: curLen = 0 if len(stack) == 0 else stack[-1][1] maxLen = max(maxLen, curLen + (i - start) + 1) # print 'state:', state # print 'stack:', stack # print 'level', level return maxLen
-
func lengthLongestPath(input string) int { i, n := 0, len(input) ans := 0 var stk []int for i < n { ident := 0 for ; input[i] == '\t'; i++ { ident++ } cur, isFile := 0, false for ; i < n && input[i] != '\n'; i++ { cur++ if input[i] == '.' { isFile = true } } i++ // popd for len(stk) > 0 && len(stk) > ident { stk = stk[:len(stk)-1] } if len(stk) > 0 { cur += stk[len(stk)-1] + 1 } // pushd if !isFile { stk = append(stk, cur) continue } ans = max(ans, cur) } return ans } func max(x, y int) int { if x > y { return x } return y }