Leetcode-140-Word Break II

这种搜索的题目直接上深搜90%都能AC，不过这题属于剩下那10%，39个数据点有8个都TLE了，看来需要剪枝策略，我使用的剪枝是记录wordDict中的单词的最小长度和最大长度，这样DFS进行的时候可以省去很多不必要的搜索，但显然这样的剪枝是不够的。参考了Discuss区一个DFS+DP的解法（https://leetcode.com/problems/word-break-ii/discuss/44262/My-C%2B%2B-DP%2BDFS-solution-(4ms)），学到了一种新的剪枝策略：

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;
    }
};