[Fastest] C solution O(n) 0ms


  • 0
    Y

    no stack, O(n) solution with c

    int lengthLongestPath(char* input) {
        char* p = input;
    	int deps[255] = { 0 };
    	int maxLen = 0;
    	int tabs = 0;
    	bool isFile = false;
    	char* nameHead = input;
    	bool newDir = false;
    
    	while (*p++ != '\0') {
    		if (*p == '.') isFile = true;
    		else if (*p == '\t') tabs++;
    		else if (*p == '\n') {
    			deps[tabs] = p - nameHead;
    			if (tabs > 0) deps[tabs] += (deps[tabs - 1] + 1);
    			if (isFile && deps[tabs] > maxLen) maxLen = deps[tabs];
    			tabs = 0;
    			isFile = false;
    			newDir = true;
    		}
    		else if (newDir) {
    			nameHead = p;
    			newDir = false;
    		}
    	}
    	if (isFile) {
    		deps[tabs] = p -1 - nameHead;
    		if (tabs > 0) deps[tabs] += (deps[tabs - 1] + 1);
    		if (deps[tabs] > maxLen) maxLen = deps[tabs];
    	}
    	return maxLen;
    }
    

Log in to reply
 

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