题目描述

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:
[]

算法1

DP

C++ 代码

    // f[i]: 前i个char的break结果，即s[0..i-1]的break结果，是vector<string>

    // f[i] = { for w in dict: if s[j..i]==w, then for each w' in f[j], add w'++w to f[i] }
    // f[0] = {""};
    // i=0..n

    vector<string> wordBreak(string s, vector<string>& wordDict) {

        // check if it's breakable. Otherwise, extreme case will TLE.
        if(! wb1(s, wordDict)) return vector<string>();

        int n = s.size();

        vector<vector<string>> f(n+1, vector<string>());
        f[0].push_back("");

        for(int i=1; i<=n; i++) {
            for(const auto& w: wordDict) {
                int j = i-w.size();
                if( j>=0 && s.substr(j, w.size())==w) {
                    for(const auto& ts : f[j]) {
                        f[i].push_back( ts.size()==0? w : ts+ " " + w);
                    }
                }
            }
        }

        return f[n];
    }

        // f[i]: 前i个char可以被break，即 s[0..i-1]
    // i = 0..n
    // f[i] = { for w in dict: if s[j:i-1]==w and f[j] }
    // init: f[0] = true

    bool wb1(string s, vector<string>& wordDict) {
        int n = s.size();

        vector<bool> f(n+1, false);
        f[0] = true;

        for(int i=1; i<=n; i++) {
            for(const auto& w : wordDict) {
                int j = i-w.size();  // i-1 - j +1 = w.size()

                f[i] = j >= 0 && w == s.substr(j, w.size()) && f[j];

                if( f[i] ) { break; }
            }
        }

        return f[n];
    }