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 题解。
此题不同之处在于，需要将计算过程记录下来，后面根据记录的计算过程构造最优解。

AC 代码

class Solution 
{
private:
    // Compute the value of an optimal solution, in a bottom-up fashion.
    // 返回值表示是否能成功分割
    void ComputeOptSolutionValue(string s, const vector<string>& wordDict, 
                                 vector<vector<bool>>& frontWordBreak)
    {
        // 初始化:定义空串能被空串拼凑出
        frontWordBreak[0][0] = true;

        // 自底向上计算最优解的值
        for(size_t i = 1; i <= s.size(); ++i)
        {
            for(size_t j = 1; j <= wordDict.size(); ++j)
            {
                if(wordDict[j-1].size() > i) continue;

                if(s.substr(i-wordDict[j-1].size(), wordDict[j-1].size()) == wordDict[j-1])
                {
                    for(size_t k = 0; k <= wordDict.size(); ++k)
                    {
                        frontWordBreak[i][j] =
                            (frontWordBreak[i][j] || frontWordBreak[i-wordDict[j-1].size()][k]);
                    }
                }
            }
        }
    }

    // Construct an optimal solution from computed infomation.
    void ConstructOptSolution(const vector<string>& wordDict,
                              const vector<vector<bool>>& frontWordBreak, 
                              int curPos, vector<string>& recordSolution, 
                              vector<vector<string>> & solutions)
    {
        if(curPos == 0)
        {
            solutions.push_back(recordSolution);
        }

        for(size_t i = 1; i <= wordDict.size(); ++i)
        {
            if(curPos >= wordDict[i-1].size() && frontWordBreak[curPos][i] == true)
            {
                recordSolution.push_back(wordDict[i-1]);
                curPos-wordDict[i-1].size(), recordSolution, solutions);
                recordSolution.pop_back();
            }
        }
    }
public:
    vector<string> wordBreak(string s, vector<string>& wordDict) 
    {
        // frontWordBreak[i][j]: s 的前 i 个 字符是否是由 wordDict 构成（要求其后缀是 wordDict[j-1]）
        vector<vector<bool>> frontWordBreak(s.size()+1);
        for(size_t i = 0; i < frontWordBreak.size(); ++i)
        {
            frontWordBreak[i].resize(wordDict.size()+1, false);
        }

        ComputeOptSolutionValue(s, wordDict, frontWordBreak);

        // 构造最优解
        vector<string> recordSolution;
        vector<vector<string>> solutions;
        ConstructOptSolution(wordDict, frontWordBreak, s.size(), recordSolution, solutions);

        vector<string> ans;
        for(size_t i = 0; i < solutions.size(); ++i)
        {
            string str;
            for(size_t j = 0; j < solutions[i].size(); ++j)
            {
                if(j == 0) str += solutions[i][j];
                else str =  solutions[i][j] + " " + str;
            }

            ans.push_back(str);
        }
        return ans;
    }
};