simple c++ O(n) solution with stack


  • 0
    G
    class Solution {
    public:
        int lengthLongestPath(string input) {
            stack<int> st;
            st.push(0);
            int res = 0;
            int n = input.size();
            int i = 0, level = 0;
            while(i < n){
                int tempLevel = 1;
                while(i<n && input[i] == '\t') {          //calculate the current level
                    ++i;
                    ++tempLevel;
                }
                if(tempLevel <= level){
                    while(level >= tempLevel){
                        st.pop();
                        --level;
                    }
                }
                bool file = false;
                int temp = i;
                while(i<n && input[i]!='\n'){
                    if(input[i] == '.') file = true;
                    ++i;
                }
                if(file){
                    res = max(res, st.top() + (i-temp));        //store the max length
                }
                else{
                    st.push(st.top() + (i-temp) + 1);           //additional 1 for directory '/'
                    ++level;
                }
                ++i;
            }
            
            return res;
        }
    };
    

Log in to reply
 

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