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 <= 10⁴
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
}

388 - Longest Absolute File Path

Question

Algorithm

Code

All Problems

All Solutions

Welcome to Subscribe On Youtube

Question

Algorithm

Code

All Problems

All Solutions