AC C++ old school need to simplify...

  • 0
    class Solution {
        unordered_map<string, vector<string>> map;
        vector<string> wordBreak(string s, vector<string>& wordDict) {
            if(map.count(s)) return map[s];
            vector<string> result;
            for (int i = 1; i < s.size(); i++)
            	string temp=s.substr(0,i);
            	if(find(wordDict.begin(), wordDict.end(), temp)!=wordDict.end())
            		vector<string> rest= wordBreak(s.substr(i), wordDict);
            		//if(rest.empty()) continue; //empty means no word //if not find, continue. combine function help return empty if rest empty, no need to check
        			combine(temp, rest);
        			// void insert (iterator position, InputIterator first, InputIterator last);
        			result.insert(result.end(),rest.begin(), rest.end()); 
            //move here make sure["app","ap","a","pp","p"]
            if(find(wordDict.begin(), wordDict.end(), s)!=wordDict.end()) 
                result.push_back(s); //check all first
            return result;
        void combine(string s, vector<string>& word)
            //if(word.empty()) word.push_back(s); //if word empty no need
        	for(int i=0; i<word.size(); i++)
        		word[i]=s+" "+word[i];

Log in to reply

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