One more solution adapted from Word Break I


  • 0
    Y
    void collect(const string& s, vector< vector< int> >& words, int i, const string& str, vector< string >& result){
    	for (int j : words[i]){
    		string new_str;
    		new_str = s.substr(i - j, j);
    		if (!str.empty()){
    			new_str += " ";
    			new_str += str;
    		}
    		if (i - j > 0)
    			collect(s, words, i - j, new_str, result);
    		else
    			result.push_back(new_str);
    	}
    }
    
    vector<string> wordBreak(string s, unordered_set<string> &dict) {
    	int len = s.length();
    	vector< vector< int> > words;
    	words.resize(len + 1);
    	int i;
    	for (i = 1; i <= len; ++i){
    		for (int j = 0; j<i; ++j)
    			if ( !j || !words[j].empty() ) {
    			if (dict.find(s.substr(j, i - j)) != dict.end())
    				words[i].push_back( i-j );
    			}
    	}
    	// unwind
    	vector< string > result;
    	collect(s, words, len, string(), result);
    	return result;
    }

Log in to reply
 

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