True DP with no "time limit exceeded" errors for both the cases of "aaaaaaaaa....ab" and "baaaaa...a"


  • 0
    G
    class Solution {
    private:
        void myWordBreak(
            const string& s,
            const unordered_map<unsigned int, vector<unsigned int> >& breaks_map,
            int end,
            vector<string>& ret)
            {
                if(end == 0)
                {
                    ret.push_back("");
                    return;
                }
                auto iter = breaks_map.find(end);
                if(iter == breaks_map.end())
                    return;
                for(unsigned int i=0; i<iter->second.size(); ++i)
                {
                    vector<string> prev_ret;
                    myWordBreak(s, breaks_map, iter->second[i], prev_ret);
                    for(unsigned int j=0; j<prev_ret.size(); ++j)
                    {
                        if(prev_ret[j] != "")
                            ret.push_back(prev_ret[j] + " " + s.substr(iter->second[i], end - iter->second[i]));
                        else
                            ret.push_back(s.substr(iter->second[i], end - iter->second[i]));
                    }
                }
            }
    public:
        vector<string> wordBreak(string s, unordered_set<string>& wordDict) {
            vector<string> ret;
            if(s.length() == 0 && wordDict.size() == 0)
                return ret;
            unordered_map<unsigned int, vector<unsigned int> > breaks_map;
            breaks_map.emplace(0, vector<unsigned int>(1, 0));
            for(unsigned int i=0; i<s.length(); ++i)
            {
                vector<unsigned int> current_breaks;
                for(auto iter = breaks_map.begin(); iter != breaks_map.end(); ++iter)
                {
                    unsigned int start = iter->first;
                    string word(s.substr(start, i+1-start));
                    if(wordDict.find(word) != wordDict.end())
                        current_breaks.push_back(start);
                }
                if(current_breaks.size() > 0)
                    breaks_map.emplace(i+1, current_breaks);
            }
            
            auto iter = breaks_map.find(s.length());
            if(iter == breaks_map.end())
                return ret;
            myWordBreak(s, breaks_map, s.length(), ret);
            return ret;
        }
    };

Log in to reply
 

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