本文共 1718 字，大约阅读时间需要 5 分钟。

题目链接：https://leetcode.com/problems/word-break-ii/

Given a string s and a dictionary of words dict, add spaces in s to construct a sentence where each word is a valid dictionary word.

Return all such possible sentences.

For example, given
s = "catsanddog",
dict = ["cat", "cats", "and", "sand", "dog"].

A solution is ["cats and dog", "cat sand dog"].

思路: DFS+部分剪枝, 搜索的时候记录后面的状态, 如果后面不能搜到, 那么就直接返回了, 否则就进行下去. 其实这样的效率并不高, 因为剪枝并不完全, 即后面可以找到的话, 还要再搜一遍. 估计数据量并不大. 

代码如下:

class Solution {public:    void DFS(string& s, unordered_set
   
    & wordDict, string str, int k)    {        if(k >= s.size()) result.push_back(str.substr(1));        if(hash.count(k) && hash[k] == false) return;        for(int i = k; i < s.size(); i++)        {            string tem = s.substr(k, i-k+1);            if(wordDict.count(tem))            {                int len = result.size();                DFS(s, wordDict, str + " " + tem, i+1);                hash[i+1] = (len != result.size());            }        }    }        vector
    
      wordBreak(string s, unordered_set
     
      & wordDict) {        DFS(s, wordDict, "", 0);        return result;    }private:    vector
      
        result;    unordered_map
       
         hash;};
       
      
     
    
   

所以还有一种更为彻底的bottom-up如下:

class Solution {public:    vector
   
     wordBreak(string s, unordered_set
    
     & dict) {        if(hash.count(s)) return hash[s];        vector
     
       result;        if(dict.count(s)) result.push_back(s);        for(int i=1; i
      
        vec = wordBreak(s.substr(0, i), dict);            for(auto val: vec) result.push_back(val+" " +word);        }        return hash[s]=result;     }    private:    unordered_map
       
        > hash;};
       
      
     
    
   

转载地址：http://eilbn.baihongyu.com/