Longest Absolute File Path Solutions in C++

// Source : https://leetcode.com/problems/longest-absolute-file-path/
// Author : Hao Chen
// Date   : 2016-08-23



class Solution {
public:
    // Solution
    // --------
    // We can see the input formation has the order
    // so, we can maintain an array which states the current level's path length
    //
    // For example:
    //    dir
    //        subdir1            <- length[ level1 = len("dir")+len("/"), 
    //                                      level2 = len("dir")+len("/")+len("subdir1")+len("/") ] 
    //           file.ext
    //        subdir2
    //           file.ext
    //           subsubdir1     <- length[ level1 = len("dir")+len("/"), 
    //                                     level2 = len("dir")+len("/")+len("subdir2")+len("/"), 
    //                                     level3 = len("dir")+len("/")+len("subdir2")+len("/")+len("subsubdir1")+len("/") ] 
    //               file.ext  
    //
    int lengthLongestPath(string input) {
        
         stringstream ss(input); 
         string line;
         int result = 0;
         
         vector<int> length;
         length.push_back(0); //initialize top dummy level's length is zero
        
         while (getline(ss, line, '\n')) {
             //get current level, start from 1
             int level = 0;
             while ( line[level++] == '\t'); // get the level
             int len = line.size() - level + 1;

             //if is a file, then cacualte the total length.
             if (line.find('.') != string::npos) { 
                 if ( length[level-1] + len > result ) {
                    result = length[level-1] + len;
                 }
             } else {
                
                 if (length.size() <= level) {
                     length.push_back(0); 
                 }
                 
                 // if it a folder, then update the current level's length
                 length[level] = length[level-1] + len + 1; // 1 for "/" path delimiter
             }
             
         }
         return result;
    }
};

/// Source : https://leetcode.com/contest/warm-up-contest/problems/longest-absolute-file-path/
/// Author : liuyubobobo
/// Time   : 2017-10-19

#include <iostream>
#include <stack>
#include <cctype>
#include <cassert>
#include <string>

using namespace std;

// Using stack to simulate the dfs process
// Time Complexity: O(n)
// Space Complexity: O(n)
class Solution {
public:
    int lengthLongestPath(string input) {

        //cout << input << endl;

        int res = 0;
        int curLength = 0;
        stack<string> dir;

        int start = 0;
        for(int i = 1 ; i <= input.size() ; ){
            if(i == input.size() || input[i] == '\n'){

                string curStr = input.substr(start, i-start);
                //cout << "cur str: " << curStr << endl;

                int j = start;
                while(input[j] == '\t')
                    j ++;
                string curDir = curStr.substr(j-start);
                int curDepth = j - start;

                if(curDepth < dir.size()){
                    assert(dir.size() >= (dir.size() - curDepth));

                    int pop_time = dir.size() - curDepth;
                    for(int k = 0 ; k < pop_time ; k ++){
                        curLength -= dir.top().size();
                        dir.pop();
                    }
                }
                else
                    assert(curDepth == dir.size());

                dir.push(curDir);
                curLength += curDir.size();

                if(curDir.find(".") != string::npos){
                    assert(dir.size() >= 1);
                    res = max(res, curLength + (int)dir.size() - 1);
                }

                start = i+1;
                i = start + 1;
            }
            else
                i ++;
        }

        return res;
    }
};

int main() {

    cout << Solution().lengthLongestPath(
            "dir\n\tsubdir1\n\tsubdir2\n\t\tfile.ext") << endl;

    cout << Solution().lengthLongestPath(
            "dir\n\tsubdir1\n\t\tfile1.ext\n\t\tsubsubdir1\n\tsubdir2\n\t\tsubsubdir2\n\t\t\tfile2.ext") << endl;

    cout << Solution().lengthLongestPath(
            "a\n\tb1\n\t\tf1.txt\n\taaaaa\n\t\tf2.txt") << endl;

    return 0;
}