LeetCode 140. Word Break II

Given a non-empty string s and a dictionary wordDict containing a list of non-empty words, add spaces in s to construct a sentence where each word is a valid dictionary word. Return all such possible sentences.

Note:

• The same word in the dictionary may be reused multiple times in the segmentation.
• You may assume the dictionary does not contain duplicate words.

Example 1:

Input:
s = "catsanddog"
wordDict = ["cat", "cats", "and", "sand", "dog"] 
Output:
[
   "cats and dog",
   "cat sand dog"
 ]

Example 2:

Input:
s = "pineapplepenapple"
wordDict = ["apple", "pen", "applepen", "pine", "pineapple"]
Output:
[
  "pine apple pen apple",
  "pineapple pen apple",
  "pine applepen apple"
]
Explanation: Note that you are allowed to reuse a dictionary word.

Example 3:

Input:
s = "catsandog"
wordDict = ["cats", "dog", "sand", "and", "cat"]
Output:
[]

解析：此题目是在LeetCode 139. Word Break上进行的增加，139只要求判断能否分割成词典中的词语，这里要求输出所有的组合。在139题目基础上进行调整。还是采用动态规划的方法来做，同时用一个二维数组state来记录状态，即当前的状态是由前面的哪个状态转移而来。这样方便后面进行回溯。回溯的过程采用深度优先遍历，假设当前位置为k，当前位置可能由多个位置转移而来，则遍历state[k]所有的状态，然后拼接字符。具体代码如下：

class Solution {
public:
    vector<string> wordBreak(string s, vector<string>& wordDict) {
        int len = s.size();
        vector<string> result;
        vector<vector<int>> state(len+1);
        vector<bool> dp(len+1, false);
        unordered_set<string> wordSet(wordDict.begin(), wordDict.end());
        dp[0] = true;
        for(int i=0; i <=len; i++)
        {
            for(int j=0; j < i; j++)
            {
                string temp = s.substr(j, i-j);
                if(dp[j] && wordSet.find(temp) != wordSet.end())
                {
                    dp[i] = true;
                    state[i].push_back(j);
                }
            }
        }
        string temp = "";
        if(dp[len])
            dfs(dp, state, result, s, len, temp);
        return result;
    }
    void dfs(vector<bool>& dp, vector<vector<int>>& state, vector<string>& res, string& s, int& pos, string temp)
    {
        if(pos == 0)
        {
            res.push_back(temp);
            res.back().pop_back();
            return;
        }
        for(auto pre : state[pos])
        {
            dfs(dp, state, res, s, pre, s.substr(pre, pos-pre) + " " + temp);
        }
    }
 };