C++ O(n) time stack solution


  • 1
    F

    The idea is using a stack to track the current length of longest prefix. If the depth doesn't match, pop the stack and update the current solution.

    class Solution {
    public:
        int lengthLongestPath(string input) {
            stack<int> st; // length of path
            int result = 0, current = 0;
            bool isfile = false;
            for (int i = 0, j = 0; j <= input.length();) {
                if (j == input.length() || input[j] == '\n') {
                    int level = getLevel(input, i, j);
                    int filename_len = j - i - level;
                    while (st.size() > level) {
                        current -= st.top();
                        st.pop();
                    }
                    if (isfile) {
                        result = max(result, current + filename_len + level);
                    } else {
                        st.push(filename_len);
                        current += filename_len;
                    }
                    i = j = j + 1;
                    isfile = false;
                } else {
                    if (input[j] == '.') isfile = true;
                    ++j;
                }
            }
            return result;
        }
        
        inline int getLevel(string& input, int i, int j) {
            int level = 0;
            while (i < j && input[i++] == '\t') ++level;
            return level;
        }
    };
    

Log in to reply
 

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