My C++ simple solution


  • 0
    K
     class Solution {
    public:
        void traverse(vector<vector<string>> & matched_words, int n, vector<string> & res, string temp) {
            if (n <= 0) {
                res.push_back(temp);
            } else {
                for (int i = 0; i < matched_words[n].size(); i++) {
                    string new_temp = matched_words[n][i];
                    if (temp.size() > 0) {
                        new_temp = new_temp + " ";
                        new_temp = new_temp + temp;
                    }
                    traverse(matched_words, n - matched_words[n][i].size(), res, new_temp);
                }
            }
            
        }
    
        vector<string> wordBreak(string s, unordered_set<string>& wordDict) {
            vector<string> res;
            
            vector<int> d;
            vector<vector<string>> matched_words;
            int i = 0;
            for (i = 0; i <= s.size(); i++) {
                d.push_back(0);
                vector<string> words;
                matched_words.push_back(words);
            }
            d[0] = 1;   // initial value for DP[0]
            
            // iterate from DP[1] to DP[n]
            for (int i = 1; i <= s.size(); i++) {
                // check if exist k, d[k] == 1 && s[k..(i-1)] exist in wordDict
                for (int k = 0; k < i; k++) {
                    if (d[k] == 0) continue;
                    
                    // check if s[k..(i-1)] exist in wordDict
                    string substr = s.substr(k, i-1-k+1);
                    
                    unordered_set<string>::iterator iter;
                    for (iter = wordDict.begin(); iter != wordDict.end(); ++iter) {
                        if (iter->compare(substr) == 0) {
                            d[i] = 1;
                            matched_words[i].push_back(*iter);
                        }
                    }
                }
                
            }
            
            if (d[s.size()] == 1) {
                // traverse the trace to get the result
                string temp = "";
                traverse(matched_words, s.size(), res, temp);
            } 
            
            return res;
            
            
        }
    };

Log in to reply
 

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