a long but easy-to-understand C++ solution(can't run a weird case o(╯□╰)o)


  • 0
    S

    This is a dfs algorithm using stack(actually vector). But it can't run the case "dir\n file.txt".(so confused....i think the result of this case should be 8) Even it's long , it is easy to understand.
    '''. For a example:
    '''class Solution {
    public:
    typedef struct Element{
    int sum_to_now;
    int deepth;
    }Elem;
    int max=0;
    vector<Elem> vec;
    Elem elem1;
    bool flag = false;

    int lengthLongestPath(string input) {
    	int n = 0;
    	for (; n < input.size()&& input[n] != '\n'; n++)
    	{
    		if (input[n] == '.')
    			flag = true;
    	}
    	if (flag)
    	{
    		flag = false;
    		max = n;
    	}
    	elem1.deepth = 0;
    	elem1.sum_to_now = n;
    	vec.push_back(elem1);
    
    	for (int i =n;i<input.size();)
    	{
    		if (input[i] == '\n')
    		{
    			i++;
    			int deepth = 0;
    			int sum_to_now =  vec.back().sum_to_now;
    			for (; input[i] != '\n'&&i< input.size(); i++)
    			{
    				if (input[i] == ' ')
    					continue;
    				if (input[i] == '\t')
    					deepth++;
    				if (input[i] != '\t')
    				{
    					sum_to_now++;
    					if (input[i] == '.')
    						flag = true;
    				}
    
    			}
    
    			if (deepth > vec.back().deepth)
    			{
    				Elem elem;
    				elem.deepth = deepth;
    				elem.sum_to_now = sum_to_now;
    				vec.push_back(elem);
    				goto out;
    			}
    			if (deepth == vec.back().deepth)
    			{
    				sum_to_now -= vec.back().sum_to_now;
    				vec.pop_back();
    				Elem elem;
    				elem.deepth = deepth;
    				elem.sum_to_now = vec.size() == 0 ? sum_to_now : vec.back().sum_to_now + sum_to_now;
    				vec.push_back(elem);
    				goto out;
    			}
    			if (deepth < vec.back().deepth)
    			{
    				//deepth -= vec.back().deepth;
    				sum_to_now -= vec.back().sum_to_now;
    				for (int cnt = vec.back().deepth - deepth; cnt >= 0; cnt--)
    				{
    					vec.pop_back();
    				}
    				Elem elem;
    				elem.deepth = deepth;
    				elem.sum_to_now = vec.size() == 0 ? sum_to_now : vec.back().sum_to_now + sum_to_now;
    				vec.push_back(elem);
    				goto out;
    			}
    			out:
    			if (flag)
    			{
    				flag = false;
    				if (vec.back().sum_to_now > max)
    					max = vec.back().sum_to_now+ vec.back().deepth;
    			}
    
    		}
    		else
    			i++;
    	}
    
    	return max;
    }
    

    };
    pass''''


Log in to reply
 

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