Time limited exceeded with recursive solution


  • 0
    J
    class Solution {
    public:
        bool wordBreak(string s, unordered_set<string> &dict) {
            return wb(s, dict, 0);
        }
        
        bool wb(const string& s, unordered_set<string> &dict, int i) {
        	string word;
        
        	if (i==s.size()) return true;
        
        	while(i<s.size()) {
        		int k=i;
        		while(k<s.size()) {
        			word.push_back(s[k]);
        			if (dict.count(word)) break;
        			k++;
        		}
        
        		if (k==s.size()) {
        			return false;
        		}
        		if (wb(s, dict, k+1)) return true;
        		i++;
        	}
        	return false;
        }
    };
    

    This recursive solution is giving me time limited exceeded, why?


Log in to reply
 

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