C++ solution


  • 0
    G
    class Solution {
    public:
        int lengthLongestPath(string input) {
            unordered_map<int,string> level;
            unordered_map<string,string> parent;
            int result = 0;
            for(int i=0;i<input.size();){
                int currentLevel = 0;
                bool file=false;
                while(input[i]=='\t'||input[i]=='\n'){
                    if(input[i]=='\t')   currentLevel++;
                    i++;
                }
                string str;
                while(input[i]!='\n'&&i<input.size()){
                    str.push_back(input[i]);
                    if(input[i]=='.')   file = true;
                    i++;
                }
                level[currentLevel]=str;            
                if(file){
                    int length = str.size();
                    for(int i=0;i<currentLevel;i++)
                        length = length + level[i].size()+1;
                    result = max( result, length);
                }            
            }
            return result;
        }
    };

  • 0
    G

    We can also use Dynamic Programming. It is better

    class Solution{//Dp
    public:
        int lengthLongestPath(string input){
            vector<int> result(1,0);
            int res = 0;
            
            for(int i=0;i<input.size();){
                bool file = false;
                int count = 0;
                int currentLevel = 0;
                while(input[i]=='\t'||input[i]=='\n'){
                    if(input[i]=='\t')  currentLevel ++;
                    i++;
                }
                while(input[i]!='\n'&&i<input.size()){
                    if(input[i]=='.')   file = true;
                    count++;
                    i++;
                }
                if(currentLevel==0)result[0]=count;
                else if(currentLevel >= result.size()) result.push_back(result[currentLevel-1]+count);
                else result[currentLevel]=result[currentLevel-1]+count;
                
                if(file){
                    res = max(res, result[currentLevel]+currentLevel);
                }
            }
            return res;
            
        }
    };

Log in to reply
 

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