388. Longest Absolute File Path - cocoder39/coco39_LC GitHub Wiki

388. Longest Absolute File Path

Notes 2021:

变形： return longest path rather than length of longest path

class Solution:
    def lengthLongestPath(self, input: str) -> int:
        tokens = input.split('\n')
        level_to_length = {}
        max_len = 0
        for token in tokens:
            level = token.count('\t')
            length = len(token.replace('\t', ''))
            if '.' not in token: # dir
                level_to_length[level] = length
            else: # file
                path_len = length + level
                for k in level_to_length:
                    if k < level:
                        path_len += level_to_length[k]
                max_len = max(max_len, path_len)
        return max_len

=========================

use two stacks, one stack to store each dir/file name, the other to record the corresponding identation level. attention: update res only if the token is a file (containing '.').

int lengthLongestPath(string input) {
        int res = 0, cur = 0;
        stack<string> strStk;
        stack<int> idenStk;
        
        stringstream ss(input);
        string line;
        while (getline(ss, line, '\n')) {
            int len = line.length(), cnt = 0;
            while (cnt < len && line[cnt] == '\t')  cnt++;
            while (! idenStk.empty() && cnt <= idenStk.top()) {
                string token = strStk.top();
                strStk.pop();
                idenStk.pop();
                cur -= 1 + token.length(); // "/token"
            }                
            string token = line.substr(cnt);
            strStk.push(token);
            idenStk.push(cnt);
            cur += 1 + token.length(); // "/token"
            if (token.find(".") != string::npos) { // in case no file
                res = max(res, cur);
            }
        }
        return res > 0 ? res - 1 : 0; // res - 1 to remove leading '/'  
    }
⚠️ **GitHub.com Fallback** ⚠️