Share my simple C++ solution and welcome any suggestions


  • 0
    C
    class Solution {
    //this is just a simple solution, I am sure there's much to improve
        public:
            vector<string> wordBreak(string s, unordered_set<string> &dict) {
                int len = s.length();
                for(int i=0; i<len; i++){
                    vector<int> tmp(len, 0);
                    dp.push_back(tmp);
                }
                vector<bool> reach(len, false);  // Record if we can form a valid break using former chars.
                for(int i=0; i<len; i++){
                    if(i>0 && !reach[i-1]) continue;
                    for(int j=i; j<len; j++){
                        string sub = s.substr(i, j-i+1);
                        if(dict.find(sub) != dict.end()) {
                            reach[j] = true;
                            dp[i][j] = 1;
                        }
                    }
                }
                string str = "";
                if(reach[len-1])
                    helper(0, len, str, s);
                return ans;
            }
            
            void helper(int ind, int len, string str, string s){
                if(ind == len) {
                    ans.push_back(str.substr(0, str.length()-1));
                    return;
                }
                for(int i=ind; i<len; i++){
                    if(dp[ind][i] == 1){
                        string nstr = str + s.substr(ind, i-ind+1) + " ";
                        helper(i+1, len, nstr, s);
                    }
                }
            }
            
            vector<vector<int> > dp;
            vector<string> ans;
        };

  • 0
    C

    what's the rumtime please?


Log in to reply
 

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