Two different solutions in java using stack and hashmap


  • 15
    F

    "dir\n\tsubdir1\n\t\tfile1.ext\n\t\tsubsubdir1\n\tsubdir2\n\t\tsubsubdir2\n\t\t\tfile2.ext"
    the root dir dir is in level 1, we push a initial value 0 into stack first indicating a not existing file with length 0

        public int lengthLongestPath(String input) {
            ArrayDeque<Integer> stack = new ArrayDeque<>();
            stack.push(0);
            int result = 0;
            for (String s : input.split("\n")) {
                int level = s.lastIndexOf('\t') + 1;
                int len = s.length() - level;
                while (stack.size() > level + 1) {
                    stack.pop();
                }
                if (s.contains(".")) {
                    result = Math.max(result, stack.peek() + len);
                } else {
                    stack.push(stack.peek() + len + 1);
                }
            }
            return result;
        }
    

    hashMap stores (level, the length of the path up to level level) pairs. By default, we use a (0,0) to initialize the hashmap. But for example "dir\n\tsubdir1\n\t\tfile1.ext\n\t\tsubsubdir1\n\tsubdir2\n\t\tsubsubdir2\n\t\t\tfile2.ext".
    dir is in level 1, not 0. subdir1 is in level 2, so on...
    we update the hashMap using hashMap.get(level) + len + 1 because the current level is level+1, previous level is level, we +1 because the additional path separator char \ , if s contains . , we update the current max length
    Hope helps

        public int lengthLongestPath(String input) {
            HashMap<Integer, Integer> hashMap = new HashMap<>();
            hashMap.put(0, 0);
            int result = 0;
            for (String s : input.split("\n")) {
                int level = s.lastIndexOf('\t') + 1;
                int len = s.length() - level;
                if (s.contains(".")) {
                    result = Math.max(result, hashMap.get(level) + len);
                } else {
                    hashMap.put(level + 1, hashMap.get(level) + len + 1);
                }
            }
            return result;
        }
    

  • 0
    S

    Very elegant code. Instead of hashmap, you can easily use array.


  • 0
    F

    But the size of the array is unknown, you have to give it a big initial size to avoid ArrayIndexOutOfBounds


  • 0
    S

    @fhqplzj
    input.split() will return total no of strings + 1 will be size of array.


  • 0
    J

    Change int len = s.substring(level).length(); to final int len = s.length() - level; ?


  • 0

    This is a good, clean solution!


  • 1

    Edit: My argument here is not valid and @ke8511369 explained it below
    ................................................................................
    The hashMap approach does not work in all cases.


  • 1
    K

    @yano84-msn-com
    i don't think this is wrong. when u go to Directory2, u set (key=1) map.get(0)+len+1, map.get(0) always return 0. cuz it never gets set again. so it will set (key=1) to the correct one, in ur case, still 11


  • 0

    @ke8511369 You are absolutely right! I was confused between the key (1) and the value that uses the key (0) and adds upon it. My bad.. Thanks for the explanation!


Log in to reply
 

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