6ms C++ recursive solution with memoization


  • 0
    S
    class Solution {
    public:
    
        vector<string> wordBreak(string s, vector<string>& wordDict) {
            unordered_set<string> dict(wordDict.size());
            unordered_map<int, vector<string>> memo;  
            int maxWordLength = 0; 
            for(string word: wordDict) {
                dict.insert(word);
                int wordLength = word.size();
                maxWordLength = max(maxWordLength, wordLength);
            }
            return makestrings(0, s, memo, dict, maxWordLength); 
        }
        
        vector<string> makestrings(int index, string& s, unordered_map<int, vector<string>>& memo, 
                        unordered_set<string>& dict, int maxWordLength){
            if(index==s.size()) {
                vector<string> answer; 
                answer.push_back(""); 
                memo.insert(make_pair(index, answer));
                return answer; 
            }
            auto it = memo.find(index); 
            if(it!=memo.end()){
                return it->second; 
            }
            vector<string> answer;
            for(int i = 1; i<=maxWordLength && index+i<=s.size(); i++){
                string word = s.substr(index, i);
                if(dict.find(word)==dict.end()) continue; 
                vector<string> rest = makestrings(index+i, s, memo, dict, maxWordLength);
                for(string temp: rest){
                    if(temp=="") answer.push_back(word);
                    else answer.push_back(word + " " + temp); 
                }
            }
            memo.insert(make_pair(index, answer));
            return answer; 
        }
    };
    

Log in to reply
 

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