My double DP solution: C++ with solving TLE and MLE


  • 0
    Y
    class Solution {
        public:
            vector<string> wordBreak(string s, unordered_set<string> &dict);
    };
    
    
    vector<string> Solution::wordBreak(string s, unordered_set<string> &dict) {
        int n = s.size();
        vector<bool> f; // 0 --> n - 1
        f.resize(n + 1);
        f[n] = true;
        for (int i = n - 1; i >= 0; -- i) {
            string p = s.substr(i, 1);
            f[i] = false;
            for (int j = i + 1; j < n; ++ j) {
                if (f[j] && dict.find(p) != dict.end()) {
                    f[i] = true;
                    break;
                }
                p = p + s[j];
            }
            if (!f[i])
                f[i] = dict.find(p) != dict.end();
        }
    
        // 1 --> n
        vector<string> ret[n + 1];
        ret[0].clear();
        if (!f[0]) return ret[0];
        ret[0].push_back("");
        for (int i = 1; i <= n; ++ i) {
            ret[i].clear();
            if (!f[i]) continue;
            string p = s.substr(i - 1, 1);
            for (int j = i - 1; j > 0; -- j) {
                if (!ret[j].empty() && dict.find(p) != dict.end()) {
                    for (int k = 0; k < ret[j].size(); ++ k)
                        ret[i].push_back(ret[j][k] + " " + p);
                }
                p = s[j - 1] + p; 
            }
            if (dict.find(p) != dict.end())
                ret[i].push_back(p);
        }
        return ret[n];
    }

Log in to reply
 

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