My C++ O(n) solution


  • 0
    F
    class Solution {
    public:
        int lengthLongestPath(string input) {
            vector<int> lengthAtDepth;
    
            int currentDepth = 0;
            int strStart = 0;
            int maxDepth = 0;
            bool isFile = false;
            for(int i = 0; i < input.length(); ++i){
                if(input[i] == '\n'){
                    if(currentDepth >= lengthAtDepth.size()) 
                        lengthAtDepth.resize((lengthAtDepth.size()+1)*2);
                    if(currentDepth == 0){
                        lengthAtDepth[currentDepth] = i - strStart; 
                    }
                    else{
                        lengthAtDepth[currentDepth] = lengthAtDepth[currentDepth-1] + i - strStart + 1; 
                    }                
                    if (isFile){
                        if(lengthAtDepth[currentDepth] > maxDepth) maxDepth = lengthAtDepth[currentDepth];
                    }
                    isFile = false;
                    strStart = i+1;
                    currentDepth = 0;
                }
                else if(input[i] == '\t'){
                    ++strStart;
                    ++currentDepth;
                }else if(input[i] == '.'){
                    isFile = true;
                }
            }
            if(currentDepth > 0 && isFile){
                if(lengthAtDepth[currentDepth-1] + input.length() - strStart + 1 > maxDepth) 
                    maxDepth = lengthAtDepth[currentDepth-1] + input.length() - strStart + 1; 
            }
            else{
                if(input.length() - strStart > maxDepth && isFile)
                    maxDepth = input.length() - strStart;
            }
            return maxDepth;
        }
    };
    
    

Log in to reply
 

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