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


  • 0
    class Solution {
        unordered_map<string, vector<string>> map;
    public:
        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
            map[s]=result;
            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.