Simple Python solution


  • 76

    The number of tabs is my depth and for each depth I store the current path length.

    def lengthLongestPath(self, input):
        maxlen = 0
        pathlen = {0: 0}
        for line in input.splitlines():
            name = line.lstrip('\t')
            depth = len(line) - len(name)
            if '.' in name:
                maxlen = max(maxlen, pathlen[depth] + len(name))
            else:
                pathlen[depth + 1] = pathlen[depth] + len(name) + 1
        return maxlen

  • 0
    L

    Nice solution!


  • 0
    H

    @StefanPochmann

    unbelievable short solution!


  • 3

    @StefanPochmann great job, I was only able to do this

    class Solution(object):
        def lengthLongestPath(self, input):
            paths, max_length, length, depth = [], 0, 0, 0
            for line in input.split("\n"):
                now_depth = collections.Counter(line)['\t']
                name = line.strip('\t')
                if now_depth <= depth and paths:
                    for k in range(depth - now_depth + 1):
                        last = paths.pop()
                        length -= len(last)
                        if "." not in last:
                            length -= 1
                paths.append(name)
                length += len(name)
                if "." in name:
                    max_length = max(max_length, length)
                else:
                    length += 1
                depth = now_depth
            return max_length
    
    

  • 0

    @StefanPochmann brilliant!


  • 0
    J

    @StefanPochmann
    is there a c++ version of this?


  • 0

    @hanzichi @agave I hope you also saw the cool solution from @o_sharp which is even shorter :-)

    @jeanmuu Don't know. Not by me. I don't think I'm interested enough to try it :-P


  • 0

    @StefanPochmann Damn that is good, man... But I like your version better, it's much clearer.


  • 1

    @agave What about this one then? :-D

    def lengthLongestPath(self, input):
        m, l = 0, {-1: -1}
        for s in input.split('\n'):
            d = s.count('\t')
            l[d] = 1 + l[d-1] + len(s) - d
            if '.' in s: m = max(m, l[d])
        return m

  • 0

    @StefanPochmann haha that's cool! But I still like the first one, more understandable!


  • 0

    @agave Yeah, I did go for clarity originally. I think @o_sharp's would also be very clear with variable names path/maxlen or so instead of l/maxL. But I also find it clear the way it is.


  • 1
    U

    thanks for your idea, this is a java version of your code.

      public int lengthLongestPath(String input) {
        int maxlen = 0;
        int[] pathlen = new int[input.length()+1];
        String[] st = input.split("\n");
        for(String line: st){
            String name = line.replaceAll("(\t)+","");
            int depth = line.length() - name.length();
            if(name.contains("."))
                maxlen = Math.max(maxlen, pathlen[depth] + name.length());
            else
                pathlen[depth+1] = pathlen[depth] + name.length() + 1;
        }
        
        return maxlen;
    }

  • 0
    M

    @u.u I would suggest you to use a HashMap instead of an array. I think, you are unnecessarily declaring a very huge array pathlen.


  • 0
    L

    @u.u Thanks for your java code.


  • 0
    L

    Genius!!! Thank you very much!


  • 0
    L

    @u.u Here is my java code, and I think depth 100 is enough. So the space complexity is O(1).

        public int lengthLongestPath(String input) {
            int[] prelen = new int[100];
            int maxlen = 0;
            
            for (String line : input.split("\n")) {
                int depth = line.lastIndexOf('\t')+1;
                int len = line.length()-depth;
                if (line.contains("."))
                    maxlen = Math.max(maxlen, len+prelen[depth]);
                else
                    prelen[depth+1] = prelen[depth]+len+1;
            }
            return maxlen;
        }
    

  • 0
    P

    for some reasons, when I use RUN CODE, the compiler can not tell \t from ' '(directly press space button) in the custom testcases


  • 0
    W

    nice use of lstrip!!!


  • 0

    Great solution as usual. Here's mine:

    def lengthLongestPath(self, s):
        path, out = ['/'], 0
        for p in s.split('\n'):
            old, crt, p = len(path)-1, p.count('\t'), p.lstrip('\t')
            if '.' not in p:
                if crt > old: raise Exception('must indent one level at a time')
                if old == crt:
                    path.append(p)
                else:
                    path = path[:crt+1] + [p]
                continue
            path = path[:crt+1]
            out = max(out, len('/'.join(path[1:] + [p])))
        return out
    

  • 0
    This post is deleted!

Log in to reply
 

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