My C++ DP+DFS solution (4ms)


  • 14
    D

    The basic idea is to use DP to create an array isBreakable[i] to indicate whether s[i..sSize-1] is breakable. Then we can use such information to help us speed up the DFS path build process (buildPath). Learned from other posts, I first calculated minlen and maxlen to speed up the process.

    class Solution {
    private: //DFS path build function
        void buildPath(bool isBreakable[], string &s, int pos, vector<string> &res, string curP, unordered_set<string>& wordDict, int minlen, int maxlen)
        {
            int i, len = s.size();
            for(i =minlen; i<= min(maxlen, len - pos); ++i)
                if( isBreakable[pos+i] && wordDict.count(s.substr(pos,i)) ) 
                    if(pos+i == len) res.push_back(curP + s.substr(pos,i));
                    else buildPath(isBreakable, s, pos+i, res, curP + s.substr(pos,i) + " ", wordDict, minlen, maxlen);
        }
        
    public:
        vector<string> wordBreak(string s, unordered_set<string>& wordDict) {
            int sSize = s.size(), len, i, minlen = INT_MAX, maxlen = INT_MIN;
            vector<string> res;
            bool isBreakable[sSize+1];
            fill_n(isBreakable, sSize+1, false);
                
            for (string word : wordDict) { // find the minimum and maximum word length 
                minlen = min(minlen, (int)word.length());
                maxlen = max(maxlen, (int)word.length()); 
            }        
            //DP to build isBreakable
            for(i=sSize-minlen, isBreakable[sSize]= true; i>=0; --i)
                for(len=minlen; len<=min(maxlen, sSize-i); ++len)
                {
                    if(isBreakable[i+len] && wordDict.count(s.substr(i,len)) ) {isBreakable[i] = true; break;}
                }
            //if breakable, do DFS path building
            if(isBreakable[0]) buildPath(isBreakable, s, 0, res, "", wordDict, minlen, maxlen);
            return res;
        }
    };

  • 0

    Hey @dong.wang.1694 , thank you for your brilliant solution. it's really a good idea setting a [minlen, maxlen] to cut down the runtime.


  • 0
    J

    Iterating through the dictionary to find the max word length is the best optimization we have so far. It helps to get rid of TLE combined with DP.


  • 0
    H

    Is it necessary to get DP array backwards?


Log in to reply
 

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