[recommend for beginners]clean DP C++ implementation with detailed explanation


  • -2

    Define substring[i, j] is the sub string from i to j.

      (substring[i,j] == word) :   result[i] = substring[i,j] + {result[j]}
    

    So, it's better to evaluate it backword.

    For example:

       s = "catsanddog",
       dict = ["cat", "cats", "and", "sand", "dog"].
    

    THE PROCESS:

     0  c  "cat"  -- word[0,2] + {result[3]}  ==> "cat sand dog"
              "cats" -- word[0,3] + {result[4]}  ==> "cats and dog" 
     1  a  ""
     2  t  ""
     3  s  "sand" --  word[3,6] + {result[7]} ==> "sand dog"
     4  a  "and"  --  word[4,6] + {result[7]} ==> "and dog"
     5  n  ""
     6  d  ""
     7  d  "dog"
     8  o  ""
     9  g  ""
    

    In fact, you should know that the actual process is reverse the above example.

    class Solution {
    public:
        vector<string> wordBreak(string s, unordered_set<string>& wordDict) {
            /*** result[i] : record the valid word break result of s[i, end] **/
            vector<vector<string>> result(s.size());
            for(int i=s.size()-1; i>=0; i--){
                vector<string> v;
                result[i]=v;
                for(int j=i+1; j<=s.size(); j++){
                    string word=s.substr(i, j-i);
                    if(wordDict.find(word)!=wordDict.end()){
                        if(j==s.size()){
                            result[i].push_back(word);
                        }
                        else{
                            for(int k=0; k<result[j].size(); k++){
                                result[i].push_back(word+" "+result[j][k]);
                            }
                        }
                    }
                }
            }
            return result[0];
        }
    };
    

    Referred to
    https://github.com/haoel/leetcode/blob/52222013802bab980c16b93829ba0d47ee3bf3f9/algorithms/cpp/wordBreak/wordBreak.II.cpp


  • 0

    "aaaaaaaaaaaaaaaaaaaaaaaaaaaa.....aaaaaaabaaaaaaaaaaaaaaaaaa.......aaaaaaaaaaaaaaaaaaaaaaaaa"
    ["a","aa","aaa","aaaa","aaaaa","aaaaaa","aaaaaaa","aaaaaaaa","aaaaaaaaa","aaaaaaaaaa"]

    can not be passed

    It will cause the memory limit exceeded MLE


  • 0
    J

    So why did it get a MLE? Is it because that you store all result[i]?


Log in to reply
 

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