brutal force parsing c++ solution


  • 0
    S

    I think using string stream to "split" the input may be a little faster. But in case you wouldn't mind reading a "brutal force" solution, here it is:...

    class Solution {
    public:
    	int lengthLongestPath(string input) {
    		unsigned len = 0;
    		unsigned ret = 0;
    		vector<string> dir;
    		int pos = 0;
    		string token;
    		bool isFile = false;
    		unsigned depth = 0;
    		while( (token = read(input, pos, isFile)) != "" ) {
    			if (token == "\n") {
    				while( (token = read(input, pos, isFile)) == "\t" )
    					depth++;
    			}
    
    			if(depth <= dir.size()){
    				int diff = dir.size() - depth;
    				while(diff-- > 0) {
    					len -= dir.back().size()+1 ;
    					dir.pop_back();
    					depth--;
    				}
    				dir.push_back(token);
    				depth+=1;	len += dir.back().size()+1;
    				if (isFile) ret = max(ret, len);
    			} else {
    				depth += 1;
    				len += token.size()+1;
    				dir.push_back(token);
    				if (isFile) ret = max(ret, len);
    			}
    
    			depth = 0;
    			isFile = false;
    		}
    		return ret > 0 ? ret-1 : 0 ;
    	}
    	string read(string &input, int& pos, bool &isFile) {
    		if (pos >= (int) input.size()) return "";
    		int t = pos;
    		if(input[pos] == '\n' || input[pos] == '\t') {
    			pos = pos + 1;
    			return input.substr(t, 1);
    		}
    		int i = pos;
    		while(i<(int) input.size() && input[i] != '\n' && input[i] != '\t') {
    			if (input[i] == '.') isFile = true;
    			i++;
    		}
    		pos = i;
    		return input.substr(t, pos-t);
    
    	}
    };
    

    I think this question is a little hard in some sense. It does not require any high tech data strcuture or complex algo, a simple stack job in principle. But anything about string manipulation is hard to implement without many bugs, and perhaps trial and error.


Log in to reply
 

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