Simple C++ O(n) Solution,0ms


  • 23
    X
    public:
        int lengthLongestPath(string input) {
            int maxi=0,count=0,ln=1;
            bool isFile=false;
            vector<int> level(200);
            level[0]=0;
            for(int i=0,fin=input.size();i<fin;++i){
                //find which level
                while(input[i]=='\t'){
                    ++ln;++i;
                }
                //read file name
                while(input[i]!='\n'&&i<fin){
                    if(input[i]=='.')isFile=true;
                    ++count;++i;
                }
                //calculate
                if(isFile){
                    maxi=max(maxi,level[ln-1]+count);
                }
                else{
                    level[ln]=level[ln-1]+count+1;// 1 means '/'
                }
                //reset
                count=0;ln=1;isFile=false;
            }
            return maxi;
        }
    };

  • 6
    Z

    Same as mine, but it took me some time to figure out the '\t' in string is really one char but not two char '\' and 't'.


  • 2
    W
    int lengthLongestPath(string input) {
      vector<string> lines = getLines(input);
      int numLines = lines.size();
      vector<int> lens(numLines + 1, 0);
      int maxLen = 0;
      for (auto line : lines) {
        size_t pos = line.find_last_of('\t');
        int levl = (pos == string::npos) ? 0 : (levl = pos + 1);
        if (line.find('.') == string::npos) {
          lens[levl + 1] = lens[levl] + line.size() - levl;
        } else {
          //maxLen = max(maxLen, (int)(lens[levl - 1] + line.size() + 1));
          maxLen = max(maxLen, (int)(lens[levl] + line.size() ));
        }
      }
      return maxLen;
    }
    
    vector<string> getLines(string& input) {
      istringstream iss(input);
      string curr;
      vector<string> lines;
      while (getline(iss, curr, '\n')) lines.push_back(curr);
      return lines;
    } 
    

  • 0
    B

    @zhengpenghu Yeah, so did I ......


  • 0
    Y

    Code style please. Space is free to use.


  • 4
    Y
    int lengthLongestPath(string input) {
    
        vector<int> dirs(256, 0);
        int res = 0;
        input.push_back('\n');
        
        for (int i = 0, level = 0, len = 0, isFile = 0; i < input.size(); i++) {
            switch (input[i]) {
                case '\n': level = 0; len = 0; isFile = 0; break;
                case '\t': level++; break;
                case '.' : isFile = 1;
                default:
                    len++;
                    dirs[level] = len;
                    if (isFile) res = max(res, accumulate(dirs.begin(), dirs.begin() + level + 1, 0) + level);
            }
        }
        
        return res;
    }
    

  • 0
    S

    @yuanqili you don't need to do your checking in default case for every character. Before setting level = 0; len = 0; isFile = 0 you can do accumulate and other stuff because that is the only interesting point.


  • 0
    K
    This post is deleted!

  • 0
    G

    @XORNOTXOR It's a self-explained solution, brilliant!

    I guess there is a hidden assumption in the problem: the lengths of all names in the same level are equal.

    I think in this way because you use "level[ln-1]+count", i.e. the length of a file name plus the length of any previous directory name.

    Is that so?


  • 0
    Y

    @wurourou , thumb up on your solution already.
    But I have a question here.

    Why it is not

     lens[levl + 1] = lens[levl] + line.size() - levl + 1;  // Should has '/'
    

    I can't find where it calculates '/' ?

    I know your solution is correct but just don't know where the '/' has been taken into consideration.


  • 1
    S

    @XORNOTXOR I have one question: What if the level of filepath exceeds 200? You are using hard-coded 200 as the level vector's size. Is there a reason to choose this number or it's just a random number?


Log in to reply
 

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