Java O(n) Using Stack


  • 0

    Here we use a stack to record the directory level and the string length at that level.
    Level can be the numbers of "\t".
    No need to push the string which is a file name into the stack.

    public class Solution {
        public int lengthLongestPath(String input) {
            int maxLen=0;
            LinkedList<int[]> stack=new LinkedList<>();
            for(String a : input.split("\n")){
                int level=a.lastIndexOf("\t")+1; //level equals to number of "\t" in the string
                String aa=a.substring(level);
                while(!stack.isEmpty() && stack.peek()[1]>=level) stack.pop();
                if(aa.contains(".")){
                    int len=0;
                    for(int[] t : stack) len+=t[0]+1;
                    maxLen=Math.max(maxLen,len+aa.length());
                }else{
                    stack.push(new int[]{aa.length(),level});
                }
            }
            return maxLen;
        }
    }
    

  • 0
    S

    Same idea here! However, it would be better to manually count "\t" in the prefix of filename, incase a "\t" is in the middle of the filename.

    /**
     *Basic idea:
     * stack
     *Result:
     * 25 / 25 test cases passed.
     * Status: Accepted
     * Runtime: 11 ms
     * Sorry. We do not have enough accepted submissions.
     *Date:
     * 9/2/2016
     */
    public class Solution {
        public int lengthLongestPath(String input) {
            String[] dirs = input.split("\\n");
            Stack<Integer>stack = new Stack<>();
            int maxlen = 0;
            for(String dir : dirs){
                int level = countLevel(dir);
                int filelen = dir.length()-level;
                boolean isfile = dir.contains(".");
                while(stack.size()>level){
                    stack.pop();
                }
                if(isfile){
                    int abslen = (stack.isEmpty()?0:stack.peek())+dir.length();
                    maxlen = maxlen>abslen?maxlen:abslen;
                }
                else{
                    stack.push((stack.isEmpty()?0:stack.peek())+filelen);
                }
            }
            return maxlen;
        }
        private int countLevel(String filename){
            for(int i=0;i<filename.length();i++){
                if(filename.charAt(i)!='\t')
                    return i;
            }
            return 0;
        }
    }
    

  • 0

    @skw_kevin "\t" should always be in front of file name or directory name. That's the format


  • 0
    S

    @Twins Yes, you are right! Windows only tells me none of /:*?"<>| should be in a filename, but when I tried \t, it also an invalid filename. Thanks Twins!

    BTW, how about accumulating the length of filenames in the stack, so that you don't need the inner for loop.


Log in to reply
 

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