6ms C++ recursive solution with memoization

  • 0
    class Solution {
        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) {
                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; 
                memo.insert(make_pair(index, answer));
                return answer; 
            auto it = memo.find(index); 
                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.