Python solution with detailed explanation


  • 0
    G

    Solution

    Algorithm

    1. Use a stack to solve this problem.
    2. Count of tabs gives you the depth.
    3. As you go down the depth, keep adding directories into the stack
    4. Now assume you have a stack with 3 elements. Elements within the top most sub-directory must have 3 tabs. What if it has one tab? This means that elements 3 and 2 must be popped and then this element must be added.
    5. Once you have done 4, then test for file or not and subsequently report.
    6. Note the use of count API
    class Solution(object):
        def lengthLongestPath(self, s):
            """
            :type input: str
            :rtype: int
            """
            st, max_l, c_sum = [], 0, 0
            for part in s.split("\n"):
                tabs = part.count('\t')
                part_len = len(part) - tabs
                while tabs < len(st):
                    c_sum = c_sum - st.pop()
                if "." in part:
                    max_l = max(max_l, c_sum+part_len+len(st)) # len(st) indicates "/"
                else:
                    st.append(part_len)
                    c_sum = c_sum + part_len
            return max_l
    

Log in to reply
 

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