Using tier + dp, 9ms


  • 0
    P
    class Solution {
        unordered_map<int,vector<string> > dp;
        struct tie{
            bool isWord;
            map<char,tie*> next;
            tie():isWord(false){}
        };
        void insert(tie *root, string w){
            for(auto c:w){
                if(!root->next.count(c)) root->next[c] = new tie();
                root = root->next[c];
            }
            root->isWord = true;
        }
        tie *buildTie(vector<string> &wordDict){
            auto root = new tie();
            for(auto w:wordDict) insert(root,w);
            return root;
        }
        vector<string> buildAns(tie *root,string &s,int i){
            if(i>=(int)s.size()) return vector<string>{""};
            if(dp.count(i)) return dp[i];
            dp[i] = vector<string>();
            string tmp = "";
            auto p = root;
            for(int j=i;j<(int)s.size();++j){
                if(p->isWord){
                    auto res = buildAns(root,s,j);
                    for(auto w:res) dp[i].push_back(tmp + ' ' + w);
                }
                if(!p->next.count(s[j])) return dp[i];
                p = p->next[s[j]];
                tmp += s[j];
            }
            if(p->isWord) dp[i].push_back(tmp);
            return dp[i];
        }
    public:
        vector<string> wordBreak(string s, vector<string>& wordDict) {
            tie *root = buildTie(wordDict);
            return buildAns(root,s,0);
        }
    };
    '''

Log in to reply
 

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