Does this solution needs Memoization or it implicitly handles it? This is an 16 ms AC Solution.


  • 0
    B
    public:
        
        
       void helper(string& s, unordered_set<string>& wordDict, int start, string pathString, vector<string>& res){
           
           if(start == s.size()){
               pathString.pop_back();
               res.push_back(pathString);
               return;
           }
           
           for(int i = start; i < s.length(); i++){
               
               string sub = s.substr(start,i-start+1);
               
               if(wordDict.find(sub) != wordDict.end()){
                   string tmp = pathString;
                   pathString += sub + " ";
                   helper(s,wordDict,i+1,pathString,res);
                   pathString = tmp;
               }
           }
       }
        
        vector<string> wordBreak(string s, vector<string>& wordDict) {
           string pathString = "";
           vector<string> res;
           unordered_set<string> dict;
            
            for(int i = 0 ; i < wordDict.size(); i++){
                dict.emplace(wordDict[i]);
            }
           
          if(!isWordBreak(s,dict))return res;
           helper(s,dict,0,pathString,res);
           return res;
        }
        
         bool isWordBreak(string s, unordered_set<string>& wordDict) {
            
            if(s.empty()){
                return false;
            }
            vector< vector<bool> > map(s.size(), vector<bool>(s.size(),0));
            int n = s.size();
            for(int i = 0; i< n; i++){
                for(int j = i; j < n ; j++){
                    if(wordDict.find(s.substr(i,j-i+1)) != wordDict.end()){
                        map[i][j] = true;
                    }
                }
            }
            int i = 0;
                for(int j = 0 ;j < n ;j++){
                    for(int k = 0; k < j; k++){
                        if(map[i][j] == false){
                            map[i][j] = map[i][k] && map[k+1][j];
                        }
                    }
                }
            return map[0][n-1];
        }
        
    
    };```

Log in to reply
 

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