C++ O(n) Iterative approach


  • 0
    W

    Use map to track current path length, key is the depth of the directory.
    Use curDepth to track depth of directory when doing path finding.

    int lengthLongestPath(string input) {
            unordered_map<int, int> lenthMap;
        	int curDepth = 0, maxLenth = 0;
        
        	for (int i = 0; i<input.size(); i++){
        		if (input[i] == '\n'){
        			continue;
        		}
        		else if (input[i] == '\t'){
        			curDepth++;
        		}
        		else{
        			int next = input.find_first_of("\n\t", i);
        			int fileNameLenth = ((next != string::npos) ? next : input.size()) - i;
        			string fileName = input.substr(i, fileNameLenth);			
        
        			lenthMap[curDepth] = (curDepth == 0 ? 0 : lenthMap[curDepth - 1] + 1) + fileNameLenth;
        			if (fileName.find_first_of('.', 0) != string::npos){
        				maxLenth = max(lenthMap[curDepth], maxLenth);
        			}
        			i += fileNameLenth - 1;
        			curDepth = 0;
        		}
        	}
        
        	return maxLenth;
        }
    

Log in to reply
 

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