Using tier + dp, 3ms

  • 0
    class Solution {
        struct tie{
            bool isWord;
            map<char,tie*> next;
        vector<int> dp;
        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;
        bool success(string &s,int i,tie *root){
            if(i>=(int)s.size()) return true;
            if(dp[i]>=0) return dp[i];
            auto p = root;
            for(int j=i;j<(int)s.size();++j){
                if(p->isWord && success(s,j,root)) return dp[i]=1;
                if(!p->next.count(s[j])) return dp[i] = 0;
                p = p->next[s[j]];
            return dp[i] = p->isWord;
        bool wordBreak(string s, vector<string>& wordDict) {
            int n = (int)s.size();
            dp = vector<int>(n,-1);
            auto root = buildTie(wordDict);
            return success(s,0,root);

    1, construct the tie using wordDict
    2, Looking up the whole string.

Log in to reply

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