c++ O(n) solution


  • 1
    T

    The idea is to update length of subpath, and update max-length when a file name is included (. mark)

    class Solution {
    public:
        int lengthLongestPath(string input) {
            vector<int> path_len(512, 0); // assume maximum depth of file path is 512
            stringstream ss(input);
            string tmp;
            
            int maxlen = 0;
            while (getline(ss, tmp, '\n')) {
                int d = 0; // depth of current sub-path
                while (d < tmp.size() && tmp[d] == '\t') ++d;
                string subpath = tmp.substr(d); // get length of sub-path or file name
                path_len[d] = subpath.size();
                if (subpath.find('.') != string::npos) {
                    int clen = 0;
                    for (int k = 0; k <= d; ++k) clen += path_len[k];
                    maxlen = max(maxlen, clen + d); // don't forget slash mark
                }
            }
            return maxlen;
        }
    };
    

  • 0
    B

    Elegant solution. stringstream really saves codes ;)


Log in to reply
 

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