Problem Statement

Given a string s and a dictionary of strings wordDict, add spaces in s to construct a sentence where each word is a valid dictionary word. Return all such possible sentences in any order.

Note that the same word in the dictionary may be reused multiple times in the segmentation.

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

Constraints:

• 1 <= s.length <= 20
• 1 <= wordDict.length <= 1000
• 1 <= wordDict[i].length <= 10
• s and wordDict[i] consist of only lowercase English letters.
• All the strings of wordDict are unique.

Problem Link

Word Break II - LeetCode

Code

vector<string> sentences;
vector<string> wordBreak(string s, vector<string>& wordDict)
{
    unordered_set<string> setting;
    setting.insert(wordDict.begin(), wordDict.end());
    dfs(s, "", setting);
    return sentences;
}

void dfs(string s, string sentence, unordered_set<string>& setting)
{
    if(s.empty())
    {
        sentence.pop_back();//removing " "
        sentences.push_back(sentence);
        return;
    }
    int n = s.size();
    for(int i = 1; i <= n; i++)
    {
        if(!setting.count(s.substr(0, i)))
            continue;
        dfs(s.substr(i), sentence + s.substr(0, i) + " ", setting);
    }
}