The longest absolute path in file system.


  • 1
    public int longestPath(String str){
    
    	String[] arr = str.split("\n");
    	Deque<String> stack = new LinkedList<String>();
    	int max = arr[0].length();
    	stack.addLast(arr[0]);
    	int lenSoFar = arr[0].length();
    	for(int i = 1; i < arr.length; i++){
    		String curr = arr[i];
    		int tabCount = 0;
    		int j = 0;
    		while(curr.charAt(j) == '\' && curr.charAt(j+1) == '\t'){
    			tabCount += 1;
    			j +=2;
    		}
    		while(tabCount < stack.size()){
    			lenSoFar -= stack.peekLast().length();
    			stack.removeLast();
    		}
    		int lenNoTabs = curr.length() - (2*tabCount);
    		if(isFile(curr)){
    		max = Math.max(lenSoFar + lenNoTabs + 1, max);
    		}else{
    			curr = "\" + curr.substring(2*tabCount);
    			stack.addLast(curr);
    		}
    	}
    	return max;
    }
    
    
    private boolean isFile(String st){
    	for(int j = st.length() - 1 ; j>=0; j--){
    		if(st.charAt(j) == '.'){
    			return true;
    		}
    	}
    	return false;
    }
    

  • 0
    Z

    Java implementation with stack: Stack stores path ending with previous string. When inserting a new line, while current level is smaller than or equal to stack top, pop it out.

    public int lengthLongestPath(String input) {
            int res = 0;
            if(input != null && input.length() > 0) {
                String [] strs = input.split("\n");    //NoteNote this is different from /d or /., /+ /*, does not have to escape, since it's one char
                Stack<LevelString> stack = new Stack<LevelString>();
                for(String s : strs) {
                    int level = getLevel(s);
                    while(!stack.empty() && stack.peek().level >= level) {
                        stack.pop();
                    }
                    /*String curPath = s.trim();Submission Result: Wrong Answer More Details 
                    NoteNote, can't do trim for file name might start with spaces (WTF)
    
    Input:
    "dir\n        file.txt"
    Output:
    12
    Expected:
    16
    */
                    String curPath = s.substring(level);
                    boolean isFile = false;
                    if(curPath.split("\\.").length >= 2) {  //is file
                        isFile = true;
                    }
                    if(!stack.empty()) {
                       curPath = stack.peek().s + "/" + curPath;
                    }
                    if(curPath.length() > res && isFile) {
                        res = curPath.length();
                    }
                    LevelString cur = new LevelString(level, curPath);
                    stack.push(cur);
                }
            }
            return res;
        }
        
        int getLevel(String s) {
            int res = 0;
            while(res < s.length() && s.charAt(res) == '\t') {
                res++;
            }
            return res;
        }
        
        class LevelString { //Stores 1. how many \t are in front, called level 2. cur string
            int level;
            String s;
            public LevelString(int level, String s) {
                this.level = level;
                this.s = s;
            }
        }
    

  • 0
    L
    This post is deleted!

  • 1
    L

    @leoleo17 said in The longest absolute path in file system.:

        int lengthLongestPath(string s) {
            int n = s.size(), res = 0;
            size_t f1 = s.find('\n');
            if(f1 == string::npos) return (s.find('.') == string::npos) ? 0 : n;
            stack<pair<string,int>> st;
            st.emplace(s.substr(0, (int)f1), 0);
            int i = (int)f1 + 1;
            s += '\n';
            while(i < n) {
                int ntab = 0;
                while(s[i] == '\t') {
                    ntab++;
                    i++;
                }
                while(ntab < st.top().second+1 && s.substr(i,4) == "    ") {
                    ntab++;
                    i += 4;
                }
                while(!st.empty() && st.top().second >= ntab) {
                    st.pop();
                }
                int end = s.find('\n', i);
                string cur = s.substr(i, end-i);            
                if(cur.find('.') != string::npos) { 
                    string name = st.top().first + "/" + cur;
                    res = max(res, (int)name.size());
                }
                else {
                    if(!st.empty()) cur = st.top().first + "/" + cur;
                    st.emplace(cur, ntab);
                }
                i = end+1;
            }
            return res;
        }
    

  • 0
    R

    O(n) solution, uses stack and arraylist

             Stack<String> st = new Stack<String>();
    	ArrayList<Integer> al = new ArrayList<Integer>();
    	String str = "dir\n\tsubdir1\n\t\tfile1.gif\n\t\tsubsubdir1\n\tsubdir2\n\t\tsubsubdir2\n\t\t\tfile2.ext";
    	String s[] = str.split("\n");
    	st.push("/");
    	al.add(0);
    	
    	for(String a : s)
    	{
    		if(a.contains(".gif")||a.contains(".png"))
    		{
    			String ab = "" ;
    			if(st.peek() != null)
    			ab = st.peek();
    			ab = ab+a.substring(a.lastIndexOf('\t')+1,a.length());
    			System.out.println(ab);
    			continue;
    		}
    		if(a.contains("."))
    		{
    			continue;
    		}
    		int space;
    		int i =0;
    		while(a.charAt(i) == '\t')
    		{
    			i++;
    		}
    		space = i+1;
    		int prev= al.get(al.size()-1);
    		while(prev >= space)
    		{
    			al.remove(al.size()-1);
    			st.pop();
    			prev = al.get(al.size()-1);
    		}
    		String ab = "";
    		if(st.peek() != null)
    			ab = st.peek();
    		ab=ab+a.substring(i,a.length())+"/";
    		st.push(ab);
    		al.add(space);
    		System.out.println(ab);
    	}

  • 0
    M

    @rakeshdrk Are you missing the return value?


  • 0
    R

    @mithmatt I used sysouts.


  • 0
    R

    And that's mine Python solution:

    def longest_path(folder_tree):
        stack = list()
        max_path = (0, 1, None)
        for j, line in enumerate(folder_tree.splitlines()):
            for i, current in enumerate(line):
                if current != ‘\t’:
                    break;
    	while len(stack) >= i:
                stack.pop()
    	if i > 0:
                total_legth = stack[-1] + (1 + len(line) - i)
    	else:
                total_legth = len(line)
    	
            name = line[i:]
    	if “.” in name:
                max_path = max(max_path, (total_legth, -j, ))
            else:
                stack.append(total_length)
        return max_path[2]
    

  • 0
    N

    @adrianhihi Where is your code for longest path? And what are the spaces for, it is not asked in the question?


  • 0
    E

    So I gave this a try with Javascript...:
    The idea was to build a hierarchy, keeping track of the max length / filepath along the way.

    You'd only ever need to grab the last one from the previous hierarchy, so that comparison shouldn't factor into the time complexity. The outermost loop goes through all of the characters once, so it should be O(n) - if I somehow got that wrong, please let me know!

      var longestPath = function(dirString) {
        var dirs = [];
        var startIndex = 0;
        var level = 0;
        var name, dir, maxLength = -1;
        var maxPath = prevPath = "";
    
        dirString += '\n';
        for (var i=0; i<dirString.length; i++) {
          if (dirString[i] == '\t') {
            level++;
            startIndex++;
          }
          if (dirString[i] == '\n') { // found a name
            name = dirString.substr(startIndex, i - startIndex);
    
            var dir = dirs;
            for (var j=0; j<level; j++) {
              prevPath = dir[dir.length-1].path;
              dir = dir[dir.length-1].li;
            }
            pathName = prevPath ? prevPath + '/' + name : name;
            dir.push({'path': pathName, 'li': []});
    
            level = 0;
            startIndex = i + 1;
    
            if ( pathName.length > maxLength ) {
              maxLength = pathName.length;
              maxPath = pathName;
            }
          }
        }
        return maxPath;
      };
    

  • 0
    D

    take away.
    '''
    int lengthLongestPath(string input) {
    if (input.empty()) {
    return 0;
    }
    int result = 0;
    std::istringstream iss(input);
    std::string line;
    std::unordered_map<int, int> m{{0, 0}};
    while (std::getline(iss, line)) {
    int level = line.find_last_of('\t') + 1;
    int length = line.substr(level).size();
    if (line.find('.') != std::string::npos) {
    result = std::max(result, m[level] + length);
    } else {
    m[level + 1] = m[level] + length + 1;
    }
    }
    return result;
    }
    '''


  • 2
    R

    @kecen said in The longest absolute path in file system.:

    dir/subdr2/subsubdir2/file.ext

    There is a typo

    "dir/subdir2/subsubdir2/file2.ext" so ans is 32 and not 30.


  • 0
    S
    This post is deleted!

  • 0
    P

    Short javascript solution with O(n) complexity

    const countMax = (s) => {
        let acc = []
            , soFarMax = 0
            , countByDir = (n)=>/^.+\.\w+$/.test(n)?0:1
            ;
    
        s.split("\n").forEach(item => {
                let infos = /(\t*)([\w.]+)/.exec(item)
                    , level = infos[1].split("\t").length - 1
                    , name = infos[2]
                    ;
                acc[level] = (level == 0)
                    ? name.length + countByDir(name)
                    : acc[level - 1] + name.length + countByDir(name);
                soFarMax = Math.max(acc[level], soFarMax);
            }
        );
    
        return soFarMax;
    };
    

  • 1

    Cleaner and Simpler !

    public int _lengthLongestPath2(String input) {
    	int maxLength = 0, pathLength = 0, currentDepth = 0, idx = 0, len = input.length();
            Stack <Integer> stk = new Stack<>();
            
            while (idx < len) {
                boolean isFile = false;
                int currentLength = 0;
                
                while (stk.size() > currentDepth) pathLength -= stk.pop();
                
                for (; idx < len && input.charAt(idx) != '\n'; idx ++, currentLength ++) 
                    if (input.charAt(idx) == '.') isFile = true;
                
                idx ++;
                if (isFile) maxLength = Math.max (maxLength, pathLength + currentLength);
                else pathLength += stk.push (currentLength + 1);
                
                for (currentDepth = 0; idx < len && input.charAt(idx) == '\t'; idx ++, currentDepth ++); 
            }
            
            return maxLength;
    }
    

  • 0
    H

    @alex.shuaibo.gaogmail.com
    here is my solution, main idea is:first split string to lines by "\n";then parse lines one by one,split line to parts by "\t", if current part is file,check and update maxPath.

    public static void main(String[] args) {
        Assert.assertEquals(getLongestPath("dir\n\tsubdir1\n\t\tfile1.ext\n\t\tsubsubdir1\n\tsubdir2\n\t\tsubsubdir2\n\t\t\tfile2.ext"),"dir/subdir2/subsubdir2/file2.ext");
        Assert.assertEquals(getLongestPath("dir\n\tsubdir1\n\tsubdir2\n\t\tfile.ext"),"dir/subdir2/file.ext");
        Assert.assertEquals(getLongestPath("dir"),"");
        Assert.assertEquals(getLongestPath(""),"");
        Assert.assertEquals(getLongestPath(null),"");
    }
    
    private static String getLongestPath(String s) {
        if (s == null || s.equals("")) { return ""; }
        String[] prefix = new String[100];
        String[] lines = s.split("\\n");
    
        String maxPath = "";
        for (String line : lines) {
            String[] parts = line.split("\\t");
            for (int i = 0; i <= parts.length - 1; i++) {
                if (!parts[i].equals("")) {
                    prefix[i] = parts[i];
                    if (parts[i].contains(".ext")) {
                        String path = getPath(prefix, i);
                        if (path.length() > maxPath.length()) {
                            maxPath = path;
                        }
                    }
                }
            }
        }
    
        return maxPath;
    }
    
    private static String getPath(String[] prefix, int i) {
        String root = prefix[0];
        for (int cur = 1; cur <= i; cur++) {
            root = String.join("/", root, prefix[cur]);
        }
        return root;
    }

  • 0

    This is my solution in JAVA using two Stacks.
    The solution runs in O(n).

    package difficultyModerate;
    
    import java.util.Stack;
    
    public class LongestAbsolutePath 
    {
    	public static void main(String[] args) 
    	{		
    		//String path = "dir\n\tsubdir1\n\t\tfile1.ext\n\t\tsubsubdir1\n\tsubdir2\n\t\tsubsubdir2\n\t\t\tfile2.ext";
    		String path = "dir\n\tsubdir1\n\tsubdir2\n\t\tfile.ext";
    		Stack<PathNode> stk = new Stack<PathNode>();
    
    		String[] lines = path.split("\n");
    		
    		 
    		for(int x=0;x<lines.length;x++)
    		{
    			int level=0;
    			String line = lines[x];
    			while(level<line.length())
    			{
    				if(line.charAt(level)=='\t')
    				{
    					level++;				
    				}
    				else
    				{
    					break;
    				}
    			}			
    			if(stk.isEmpty() || stk.peek().level<level)
    			{
    				stk.push(new PathNode(line.substring(level), level));
    			}
    			else if(stk.peek().level>=level)
    			{
    				while(stk.peek().level>=level)
    					stk.pop();
    				stk.push(new PathNode(line.substring(level), level));
    			}
    		}
    		
    		Stack<PathNode> stkTemp = new Stack<PathNode>();
    		while(!stk.empty())
    		{
    			stkTemp.push(stk.pop());
    		}
    		
    		while(!stkTemp.empty())
    		{
    			System.out.print(stkTemp.pop().data+"/");
    		}
    		
    	}
    	
    	
    }
    class PathNode
    {
    	int level;
    	String data;
    	
    	PathNode(String data, int level)
    	{
    		this.data = data;
    		this.level = level;
    	}
    }
    

  • 0
    E

    @ericfernat-gmail.com Apologies for the messy code. Could have organized the code into separate functions according to their distinct tasks, but yeah, whatever!


  • 0
    F

    Guys, passing an interview is not about just having a code that works, it's also about having a code that is readable and well written. Do not hesitate to separate tasks into other functions, and use new structures or classes when it makes sense.

    Here's my JavaScript tentative:

    function longestPath(fs) {
      // stack stores the length of the current folder's path
      const stack = [0];
      let currentLevel = -1;
      let i = 0;
      let max = 0;
    
      // Browse the file system and process each asset as they come
      while (i < fs.length) {
        const {name, level} = nextAsset(fs, i);
        i += name.length + level + 1;
        // When we reach a file, we check for maximum path length
        if (isFile(name)) {
          max = Math.max(max, stack[stack.length-1] + name.length);
          continue;
        }
    
        // When we access a child directory
        if (level > currentLevel) {
          stack.push(stack[stack.length-1] + name.length + 1);
          currentLevel = level;
        }
        // When we return to a parent directory
        else {
          let diff = currentLevel - level;
          while (diff--) { stack.pop(); }
          currentLevel = level;
        }
      }
      return max;
    }
    
    /* Extract the next asset name and its level in files hierarchy */
    function nextAsset(fs, i) {
      let name = '';
      let level = 0;
      while (i < fs.length && fs[i] !== '\n') {
        if (fs[i] === '\t') { level++; } else { name += fs[i]; }
        i++;
      }
      return {level, name};
    }
    
    function isFile(name) {
      return !!name.match(/.+\..+/);
    };
    
    longestPath('dir\n\tsubdir1\n\t\tfile1.ext\n\t\tsubsubdir1\n\tsubdir2\n\t\tsubsubdir2\n\t\t\tfile2.ext');
    // returns 32
    

    PS: The example given in OP message is wrong, result is 32 because they are a couple of types.


  • 0
    K

    Here's my solution using a stack:

    import java.util.Stack;
    
    public class LongestAbsolutePath {
       public static void main(String[] args) {
          String input1 = "dir\n\tsubdir1\n\tsubdir2\n\t\tfile.ext";
          String input2 = "dir\n\tsubdir1\n\t\tfile1.ext\n\t\tsubsubdir1\n\tsubdir2\n\t\tsubsubdir2\n\t\t\tfile2.ext";
          LongestAbsolutePath longestAbsolutePath = new LongestAbsolutePath();
          System.out.println(longestAbsolutePath.getLongestAbsolutePath(null));
          System.out.println(longestAbsolutePath.getLongestAbsolutePath(input1));
          System.out.println(longestAbsolutePath.getLongestAbsolutePath(input2));
       }
    
       public int getLongestAbsolutePath(String input) {
          if (input == null || input.length() == 0)
             return 0;
          Stack<String> stack = new Stack<String>();
          int prevTabs = 0;
          int clength = 0;
          int maxLength = 0;
          for (String path : input.split("\n")) {
             String sanePath = path.replaceAll("\t", "");
             int noOfTabs = path.length() - sanePath.length();
    
             int pops = prevTabs - noOfTabs;
    
             for (int i = 0; i <= pops && stack.size() > 0; i++) {
                String popped = stack.pop();
                clength -= popped.length();
             }
    
             stack.push(sanePath);
             clength += sanePath.length();
    
             if (maxLength < clength) {
                maxLength = clength;
             }
    
             prevTabs = noOfTabs;
          }
          return maxLength;
       }
    }
    

Log in to reply
 

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