my o(n) c++ solution


  • 0
    W
    class Solution {
    public:
    	int lengthLongestPath(string input) {
    		int maxlen(0);
    		vector<char> tmpname;
    		bool isfile(false);
    		vector<int> pathlenrecord;
    		int level = 0;
    		int whitespacecnt = 0;
    		bool couldbetab(false);
    		auto reset = [&](){
    			tmpname.clear();
    			isfile = false;
    		};
    		auto pathlen = [&]()->int{
    			if (pathlenrecord.empty()) return tmpname.size();
    			return pathlenrecord.back() + tmpname.size();
    		};
    		auto shrink = [&](){
    			if (level < pathlenrecord.size()) {
    				pathlenrecord.erase(pathlenrecord.begin() + level, pathlenrecord.end());
    			}
    		};
    		for (size_t i = 0; i < input.size(); ++i)
    		{
    			switch (input[i])
    			{
    			case '\n':
    				whitespacecnt = 0;
    				shrink();
    				if (isfile) {
    					maxlen = max(pathlen(), maxlen);
    				}
    				else {
    					if (pathlenrecord.empty()) pathlenrecord.push_back(tmpname.size() + 1);
    					else pathlenrecord.push_back(pathlenrecord.back() + tmpname.size() + 1);
    				}
    				level = 0;
    				reset();
    				couldbetab = true;
    				break;
    			case '\t':
    				whitespacecnt = 0;
    				level += 1;
    				reset();
    				couldbetab = true;
    				if (level == pathlenrecord.size()) couldbetab = false;
    				break;
    			case ' ':
    				whitespacecnt += 1;
    				if (couldbetab && whitespacecnt == 4) {
    					level += 1;
    					reset();
    					whitespacecnt = 0;
    					if (level == pathlenrecord.size()) couldbetab = false;
    				}
    				else if (!couldbetab) {
    					tmpname.push_back(input[i]);
    				}
    				break;
    			case '.':
    				whitespacecnt = 0;
    				tmpname.push_back(input[i]);
    				isfile = true;
    				couldbetab = false;
    				break;
    			default:
    				whitespacecnt = 0;
    				tmpname.push_back(input[i]);
    				couldbetab = false;
    				break;
    			}
    		}
    		if (!tmpname.empty() && isfile) {
    			shrink();
    			maxlen = max(pathlen(), maxlen);
    		}
    		return maxlen;
    	}
    };
    

Log in to reply
 

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