Why Time Limit Exceeded ?


  • 0
    M
    vector<string> wordBreak(string s, unordered_set<string>& wordDict) {
    	vector<string> result;
    	int len = s.length();
    	if (len == 0 || wordDict.size() == 0)
    	{
    		return result;
    	}
    	bool *opt = new bool[len];
    	for (int i = 0; i < len; i++)
    		opt[i] = 0;
    	for (int i = 0; i < len; i++)
    	{
    		string tmp = s.substr(0, i + 1);
    		if (wordDict.find(tmp) != wordDict.end())
    		{
    			//contains
    			opt[i] = true;
    		}
    		else{
    
    			for (int j = 0; j < i; j++)
    			{
    				tmp = s.substr(0, j + 1);
    				if (opt[j])
    				{
    					if (wordDict.find(tmp) != wordDict.end())
    					{
    						opt[i] = true;
    					}
    				}
    			}
    		}
    	}
    
    	if (!opt[len - 1])
    	{
    
    	}
    	else{
    
    		dfs(s, 0, wordDict, "", opt, result);
    	}
    
    	return result;
    }
    
    void dfs(string s, int index, unordered_set<string>& dict, string stack, bool* opt, vector<string> & result)
    {
    	int len = s.length();
    	if (index == len)
    	{
    		result.push_back(stack);
    		return;
    	}
    	else
    
    		for (int i = index; i < len; i++)
    		{
    			if (opt[i])
    			{
    				string tmp(s, index, i - index + 1);
    				if (dict.find(tmp) != dict.end())
    				{
    					if (stack == "")
    						dfs(s, i + 1, dict, tmp, opt, result);
    					else
    						dfs(s, i + 1, dict, stack + " " + tmp, opt, result);
    
    				}
    			}
    		}
    
    }

Log in to reply
 

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