The longest absolute path in file system.


  • 21
    K

    Suppose we abstract our file system by a string in the following manners:

    The string "dir\n\tsubdir1\n\tsubdir2\n\t\tfile.ext" represents:

    dir
        subdir1
        subdir2
            file.ext
    

    a directory dir contains an empty sub-directories 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
    

    a directory dir contains two sub-directories subdir1 and subdir2. subdir1 contains a file file1.extand an empty second-level sub-directory subsubdir1. subdir2 contains 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. That is, for example, in the second example above, the longest absolute path is "dir/subdr2/subsubdir2/file.ext", and its length is 30.

    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. Simply put, that is the length of a valid path that ends with a file, and a file contains . and an extension.

    Time complexity required: O(n) where n is the size of the input string.

    Notice that a/aa/aaa/file1.txt is not the path you want, if there is aaaaaaaaaaaaaaaaaaaaa/sth.png.


  • 1

    is there any implementation for this?


  • 4
    S

    I decided to take a crack at this. This is a graph/tree problem which consists of two parts:

    1. Parse the directory tree into graph nodes.
    2. Use depth-first search with a modified Dijkstra's algorithm in order to find the maximum distance from the root node to any file node.

    For paths that don't end in a file, I decided to return -1 as an error condition.

    Here is the code (and some test cases) in Python:

    # Basic graph node class for this problem
    class GraphNode(object):
        def __init__(self, string):
            self.string = string
            self.length = len(string)
            if '.' in self.string: # simplification to find files, could use a regex here for something more intensive
                self.file = True
            else:
                self.file = False
            self.adjacent = []
        def __repr__(self):
            return '<GraphNode {}>'.format(self.string)
    
    class Solution(object):
        def longest_dir_path(self, path):
            cur_str = '' # store the current string that we are processing
            last_root = {} # stores the last root that was found for a certain level
            level = 0 # current tree level that we are on
    
            """
            Parse the path.
    
            \t denotes a new level
            \n denotes a new node
    
            """
            path += '\n' # terminate path by \n so we get the last node
            for n in path:
                if n == '\t':
                    level += 1
                    continue
                if n == '\n':
                    x = GraphNode(cur_str)
                    if level > 0:
                        last_root[level - 1].adjacent.append(x)
                    else:
                        root = x
                    last_root[level] = x
                    level = 0
                    cur_str = ''
                    continue
                cur_str += n
            return self.dfs(last_root[0])
    
        def dfs(self, root):
            stack = [root] # DFS stack
            visited = {} # storing visited nodes
            distance = {root: 0} # storing the distance from the root node
            pre = {root: None} # predecessors
            max_distance = 0 # maximum distance
            max_node = None # largest node
    
            while stack:
                node = stack.pop()
                if node not in visited:
                    for neighbor in node.adjacent:
                        if neighbor not in distance:
                            distance[neighbor] = 0
                        
                        # update distance with the maximum distance so far
                        if distance[neighbor] < distance[node] + node.length:
                            distance[neighbor] = distance[node] + node.length
                            pre[neighbor] = node
    
                            # update max distance and node only if the target node is a file
                            if distance[neighbor] > max_distance and neighbor.file == True:
                                max_distance = distance[neighbor]
                                max_node = neighbor
                        stack.append(neighbor)
    
            if not max_node:
                return -1 # no file, max node unknown, return -1
    
            # finally calculate length
            length = 0
            v = max_node
            while v != None: 
                length += v.length + 1 # remember the / separators
                v = pre[v]
            length -= 1 # no / separator on the root directory
            return length
    
    x = Solution()
    # some test cases
    assert x.longest_dir_path('dir\n\tsubdir1\n\t\tfile1.ext\n\t\tsubsubdir1\n\tsubdir2\n\t\tsubsubdir2\n\t\t\tfile2.ext') == len('dir/subdir2/subsubdir2/file2.ext')
    assert x.longest_dir_path('dir\n\tsubdir1\n\tsubdir2\n\t\tfile.ext') == len('dir/subdir2/file.ext')
    assert x.longest_dir_path('dir') == -1
    assert x.longest_dir_path('') == -1
    assert x.longest_dir_path('dir\n\tsubdir1') == -1

  • 2
    H

    Here is my runnable code.

    I parse the string and keep track of what level the node is. If it is not the file name, I will use a hash map<Integer, String> to store each level string. If it is a file name, it will be compared it to the maximum file path so far found and pick the longest one.

    public class LongestPath{
        public String findLongestPath(String input){
            Map<Integer, String> levels = new HashMap<>();
            int firstIndex = 0, lastIndex = 1, strLength = input.length(), maxLength, levelCount = 0, currentLevelCount;
    
            String maxPath, levelStr, filePath;
    
            while (input.charAt(lastIndex) != '\n' && lastIndex < strLength){
                lastIndex++;
            }
    
            levels.put(levelCount, input.substring(firstIndex, lastIndex));
    
            maxLength = 0;
            maxPath = "";
    
            while(lastIndex < strLength){
                lastIndex++;
    
                currentLevelCount = 0;
    
                while (input.charAt(lastIndex) == '\t'){
                    currentLevelCount++;
                    lastIndex++;
                }
    
                firstIndex = lastIndex;
    
                while (lastIndex < strLength && input.charAt(lastIndex) != '\n' ){
                    lastIndex++;
                }
    
                levelStr = input.substring(firstIndex, lastIndex);
    
                if(isFileName(levelStr)){
                    filePath = "";
    
                    for(int i = 0; i < currentLevelCount; i++)
                        filePath += levels.get(i) + "/";
    
                    filePath += levelStr;
    
                    if(filePath.length() > maxLength){
                        maxLength = filePath.length();
                        maxPath = filePath;
                    }
                }
                else {
                    levelCount = currentLevelCount;
                    levels.put(levelCount, levelStr);
                }
            }
            return maxPath;
        }
    
        public boolean isFileName(String input){
    
            for(int i = 0; i < input.length(); i++)
                if(input.charAt(i) == '.') return true;
    
            return false;
        }
    }

  • 1
    L

    I wrote this solution in ruby, it checks for the deepest file of the file system, not for the longest name, but it is very easy to change the criteria to choose the answer. The last lines are just an example I provided, I hope it helps, uncomment the puts paths to check all of the different paths of the files.

    def deepestFile(fileSystem)
    
        answer      = []
        paths       = []
        currentPath = []
    
        fileSystem.each_line do |line|
            currentSC   = line.count(" ")
            text        = line.strip
    
            currentPath = currentPath.shift(currentSC/2)
    
            if !text.include? '.'
                currentPath.push text
            else
                paths.push currentPath.join('/') << '/' << text
    
                if (currentPath.length + 1 > answer.length)
                    answer = currentPath.clone << text
                end
    
            end
        end
    
        #puts paths
        return answer
    end
    
    fileSystem =
    "Dir1\n" +
    "  Dir11\n" +
    "    hola.txt\n" +
    "    Dir112\n" +
    "      haha.rb\n" +
    "  Dir12\n" +
    "    Dir111\n" +
    "      Dir1112\n" +
    "        hehe.rb\n" +
    "  hola.jpeg\n" +
    "Dir2\n" +
    "  roro.txt\n" +
    "  za.jpg"
    
    puts deepestFile(fileSystem).join('/')

  • 0
    G

    Fun question. Here's a javascript version. I used a split in the beginning because I thought I could implement a solution faster, but in reflection I think character by character would have been faster to implement and should have a faster runtime.

    function tabCount(input) {
      if (input.charAt(0) !== '\t') { return 0; }
      var leftPointer = 0;
      var rightPointer = input.length;
      // binary search to find the max tab
      // this is necessary becase we split in the beginning
      // instead of going character by character;
      while(leftPointer < rightPointer - 1) {
        var middle = Math.ceil((rightPointer + leftPointer) / 2);
        if (input.charAt(middle) === '\t') {
          leftPointer = middle;
        } else {
          rightPointer = middle;
        }
      }
      var endTabIndex = leftPointer + 1;
      return endTabIndex;
    }
    
    function isFile(input) {
      return input.indexOf('.') >= 0;
    }
    
    function removeTrailingDirectories(currentDir, maxLength) {
      while(currentDir.length > maxLength) { currentDir.pop(); }
    }
    
    /**
      @param {string} input
      @return {string}
    */
    var longestPath = function(input) {
      if (!input || input.length === 0) { return ''; }
    
      var longestPath = '';
      var currentDir = [];
      // this could be done with a character by character check
      // instead of splitting and iterating parts
      var parts = input.split(/\n/);
      parts.forEach(function (directoryPart) {
        var endTabIndex = tabCount(directoryPart);
        var strippedName = directoryPart.substr(endTabIndex);
        if (isFile(strippedName)) {
          // we could cache joining currentDir as well.
          var longestCandidate = currentDir.join('/') + '/' + strippedName;
          if (longestCandidate.length > longestPath.length) {
            longestPath = longestCandidate;
          }
        } else {
          currentDir[endTabIndex] = strippedName;
          removeTrailingDirectories(currentDir, endTabIndex + 1);
        }
      });
      return longestPath;
    }
    

  • 2
    A
    public static int printSum(String s){
           String[] arr=s.split("\n");
           int sum=0, spaces=0;
           for(int i=arr.length-1;i>=0;i--){
               String line=arr[i];
               if(line.contains(".gif") | line.contains(".jpeg") ){
                   spaces=line.length()-line.trim().length();
               }
               if(spaces> line.length()-line.trim().length() ){
                   sum+=line.trim().length()+1;
                   spaces--;
               }
           }
           return sum;
    }

  • 7
    M

    Just use stack to track each level, and O(n) solution

    static class DirEntry {
      String dirName;
      int level;
      int curLen;
    }
    
    int getLongestAbsolutePathInFileSystem(String fileSystem_) {
      Stack<DirEntry> stack = new Stack<>();
      int maxLen = 0;
      for (String line : fileSystem_.split("\n")) {
        if (line.isEmpty()) continue;
        int curLevel = 0;
        while (line.charAt(curLevel) == '\t')
          curLevel++;
        String name = line.substring(curLevel);
        if (name.indexOf('.') > 0) { // file
          maxLen = Math.max(maxLen, (stack.isEmpty() ? 0 : stack.peek().curLen + 1) + name.length());
        } else { // dir
          while (!stack.isEmpty() && stack.peek().level >= curLevel) {
            stack.pop();
          }
          DirEntry entry = new DirEntry();
          entry.dirName = name;
          entry.level = curLevel;
          entry.curLen = (curLevel == 0 ? 0 : stack.peek().curLen + 1) + name.length();
          stack.push(entry);
        }
      }
      return maxLen;
    }
    

  • 3
    S

    Just to share a Python solution using stack to simulate a DFS process.

    def getLongestPath(filesys):
      list = filesys.splitlines();  # Parse the string into list
      st = [-1]; #-1 to cancel the path separator before root dir
      lastLevel = -1;  # depth of the last item in st
      maxLen = 0;
      for item in list:
        bareName = item.lstrip('\t');	# Strip leading '\t's
        curLevel = len(item)-len(bareName);	# Use number of '\t's to find level
        while (curLevel <= lastLevel): # cd .. to the same level as "item"
          st.pop();
          lastLevel -= 1;		
        st.append(len(bareName)+st[-1]+1);	# accumulated lenth, +1 for pathsep
        lastLevel=curLevel;
        if ('.' in item): 	# Only count "files" with an extension
          maxLen = max(maxLen, st[-1]);
      return maxLen;
    

  • 0
    J

    Python solution with a bit of regular expressions and a graph DFS. Let me know what you think :)

    from collections import deque
    import re
    
    def count_t(st):
        for i in xrange(len(st)):
            if st[i] == 't':
                continue
            else:
                break
        return i
    
    def calc_longest(path_str):
        adj_list = {}
        parts = re.findall('[\w\.]+',path_str)
        root = parts[0]
        adj_list[root] = []
        ctr = 0
        for i in xrange(len(parts)):
            if parts[i] == 't':
                ctr += 1
                continue
            parts[i] = ctr*'t'+parts[i]
            adj_list[parts[i]] = []
            ctr = 0
    
        que = deque()
        que.append(parts[0])
        i=1
        while i < len(parts):
            if not parts[i] == 'n' and not parts[i] == 't':
                num_t_curr = count_t(que[-1])
                num_t = count_t(parts[i])
                if num_t == num_t_curr+1:
                    adj_list[que[-1]].append(parts[i])
                    que.append(parts[i])
                elif num_t == num_t_curr or num_t == num_t_curr - 1:
                    que.pop()
                    i -= 1
    
            i+=1
    
        que = deque()
        visited = []
        que.append(parts[0])
        l = 0
        m = 0
        path = ''
        print adj_list
        while que:
            print que, l
            curr = que.pop()
            if len(adj_list[curr]) == 0:
                if re.search('\.\w+', curr):
                    if l + len(curr) - count_t(curr) > m:
                        m = l + len(curr) - count_t(curr)
                l -= len(curr) - count_t(curr)
            else:
                l += len(curr) - count_t(curr)
    
            if not curr in visited:
                visited.append(curr)
                for i in adj_list[curr]:
                    if not i in visited:
                        que.append(i)
    
    
         return m
    
    print calc_longest(path_str)

  • 0
    N

    @stellari ur solution is awesome! i have a question. why do u need maxLen. wouldn't it always be st[-1].
    Thanks!


  • 0
    M

    I implemented it using a stack for DFS. The stack keeps count of the length so far until the parent folder. At any point in the string, doing dfsStack.peek() would return the length from root folder to the current file's or directory's parent folder.

    import java.util.Stack;
    
    public class LongestAbsolutePathInFileSystem {
    
    	public static int getLongestAbsPath(String dirStructure) {
    
    		if (dirStructure == null || dirStructure.length() == 0)
    			return 0;
    
    		int maxLen = 0, len = 0, tabCount = 0, currLen = 0;
    		boolean isFile = false;
    		char ch;
    		Stack<Integer> dfsStack = new Stack<Integer>();
    
    		for (int i = 0; i < dirStructure.length(); i++) {
    			ch = dirStructure.charAt(i);
    
    			if (ch == '\t') {
    				tabCount++;
    			} else if (ch == '\n') {
    				while (dfsStack.size() >= tabCount + 1)
    					dfsStack.pop();
    
    				len = ((dfsStack.isEmpty()) ? 0 : dfsStack.peek()) + currLen;
    
    				if (isFile && len > maxLen)
    					maxLen = len;
    				else
    					dfsStack.push(len);
    
    				tabCount = 0;
    				currLen = 0;
    				isFile = false;
    			} else {
    				if (ch == '.')
    					isFile = true;
    				currLen++;
    			}
    		}
    
    		while (dfsStack.size() >= tabCount + 1)
    			dfsStack.pop();
    		len = ((dfsStack.isEmpty()) ? 0 : dfsStack.peek()) + currLen;
    		if (isFile && len > maxLen)
    			maxLen = len;
    
    		return maxLen;
    	}
    
    }
    

  • 0
    C
    class Solution(object):
    
        def longest_absolute_path(self, fpth):
            files = fpth.split('\n')
            max_len, _ = self._dfs(files, 0, -1)
            return max_len
    
        #return len and idx. If ends with a directory, len = 0
        def _dfs(self, files, idx, lvl):
            if idx >= len(files):
                return 0, idx
            max_len = 0
            while idx < len(files):
                cur_file = files[idx]
                cur_lvl = cur_file.count('\t')
                if cur_lvl <= lvl:
                    return max_len, idx
                cur_file = cur_file.lstrip('\t')
                if '.' in cur_file: # if cur_file is not a directory
                    max_len, idx = max(max_len, len(cur_file)), idx+1
                else:
                    nxt_len, idx = self._dfs(files, idx+1, cur_lvl)
                    if nxt_len > 0:
                        max_len = max(max_len, len(cur_file)+nxt_len+1)#+1 for the backslash
            return max_len, idx
    

  • 1
    F

    Here's another solution in python. This doesn't use dfs, but rather keeps track of the length of the longest path seen so far.

    class Solution(object):
        def longest_dir_path(self, path):
            longest_so_far = -1
            height_at_level = {-1: 0}
            level = 0
    
            for line in path.split('\n'):
                for char in line:
                    if char == '\t':
                        level += 1
                    else:
                        break
    
                string = line.strip()
                if '.' in string:
                    longest_so_far = max(longest_so_far, len(string) +
                                            height_at_level[level-1])
                else:
                    height_at_level[level] = (height_at_level[level-1] +
                                                len(string) + 1)
                level = 0
            return longest_so_far
    

  • 0
    K
    This post is deleted!

  • 0
    K

    This is my initial idea is to keep consuming the string and updating the maximum length possible at the current level of the path.

    import java.util.Arrays;
    
    public class LongestSystemPath {
    
    public static void main(String[] args) {
    	String path = "dir\n\tsubdir1\n\tsubdir2\n\t\tfile.ext";
    	// String path =
    	// "dir\n\tsubdir1\n\t\tfile1.ext\n\t\tsubsubdir1\n\tsubdir2\n\t\tsubsubdir2\n\t\t\tfile2.ext";
    	LongestSystemPath l = new LongestSystemPath();
    	System.out.println(l.longestSystemPath(path));
    }
    
    private int longestSystemPath(String path) {
    	this.idx = 1;
    	return consume(path.split("\\n"), 0) + 3;
    }
    
    private int idx;
    
    private int consume(String[] str, int depth) {
    	int max = 0;
    	while (idx < str.length) {
    		String cur = str[idx].split("\t+")[1];
    		int _depth = str[idx].length() - cur.length();
    		int len = cur.length() + 1;
    		if (depth + 1 == _depth) {
    			idx += 1;
    			len += consume(str, depth + 1);
    		} else {
    			return 0;
    		}
    		max = Math.max(max, len);
    	}
    	return max;
    }
    

    }


  • 1
    K
    //Still using stack, but I think the code is little cleaner than the previous ones.
    public static int findLongestAbsolutePath(String s) {
            int maxLength = 0, curLength = 0;
            if(s == null || s.length() == 0) return 0;
            Deque<String> stack = new ArrayDeque<>();
            String[] splits = s.split("\n");
            for(String sp : splits) {
                int tabs = 0;
                while (sp.charAt(tabs) == '\t')
                    tabs++;
                while(tabs < stack.size()) {
                    String pop = stack.pop();
                    curLength -= pop.length();
                }
                String newPart = sp.substring(tabs);
                stack.push(newPart);
                curLength += newPart.length();
                if(newPart.endsWith(".ext")) {
                    maxLength = Math.max(maxLength, curLength);
                }
            }
            return maxLength;
        }
    

  • 0
    M

    Handling all cases

    public class Solution {
        
        static class FileNode {
            public List<FileNode> childs;
            public FileNode parent;
            public boolean isFile = false;
            public String name;
            public int pathLength;
    
            public FileNode(String name) {
                this.name = name;
                this.childs = new ArrayList<FileNode>();
                this.parent = null;
            }
        }
    
        public static int lengthLongestPath(String input) {
    
            FileNode rootNode=null, node=null;
            String[] files = input.split("\n");
            if(files.length < 1) {
                return 0;
            }
            rootNode = new FileNode("root");
            rootNode.pathLength = 0;
            node = rootNode;
            int curLevel=-1, maxPath=0;
            for(String filePart: files) {
                int level =0;
                while(filePart.charAt(level) == '\t')
                    level++;
                FileNode newNode = new FileNode(filePart.substring(level));
                int partLength = filePart.substring(level).length();
    
                if(level > curLevel) {
                    //inside the previous directory
    
                } else if(level < curLevel) {
                    //parse to the corresponding level
                    for(int i=curLevel; i>= level && node!=null; i--) {
                        node = node.parent;
                    }
    
                } else if(level == curLevel) {
                    //same directory
                    node = node.parent;
                }
    
                if(node!=null && !node.isFile) {
                    node.childs.add(newNode);
                    newNode.pathLength = node.pathLength + partLength ;
                    curLevel = level;
                    newNode.parent = node;
                    node = newNode;
    
                    if (newNode.name.contains(".")) {
                        newNode.isFile = true;
                        if (newNode.pathLength > maxPath) {
                            maxPath = newNode.pathLength;
                        }
                    } else {
                        newNode.pathLength +=1; //trailing slash
    
                    }
                }
            }
            return maxPath;
        }
    }
    

  • 0
    X

    A very simple yet readable python version inspired by stellari's code:

    def lengthLongestPath(self, input):
        maxLength = 0
        prev_depth = -1
        path_len_stack = [0]
        for line in input.split("\n"):
            name = line.lstrip("\t")
            curr_depth = len(line) - len(name)
            while curr_depth <= prev_depth:
                path_len_stack.pop()
                prev_depth -= 1
            if "." in name:
                maxLength = max(maxLength, path_len_stack[-1] + len(name))
            else:
                path_len_stack.append(len(name) + 1 + path_len_stack[-1])
                prev_depth = curr_depth
        return maxLength
    

  • 0
    N

    @adrianhihi : This checks for only image files though.


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.