140. Word Break II

Posted on Edited on In

140. Word Break II

Description

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:

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

Example 2:

1
2
3
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:

1
2
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 .
  • Input is generated in a way that the length of the answer doesn’t exceed10^5.

Hints/Notes

  • 2024/07/12
  • backtracking
  • No solution from 0x3F

Solution

Language: C++

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
class Solution {
public:
    unordered_set<string> words;
    vector<string> res;
    string cur, s_;
    int minLen = INT_MAX, maxLen = 0;

    vector<string> wordBreak(string s, vector<string>& wordDict) {
        for (auto& word : wordDict) {
            words.insert(word);
            minLen = min(minLen, (int)word.size());
            maxLen = max(maxLen, (int)word.size());
        }
        s_ = s;
        traverse(0);
        return res;
    }

    void traverse(int index) {
        if (index == s_.size()) {
            res.push_back(cur);
            return;
        }
        for (int i = minLen; i <= maxLen; i++) {
            if (i + index > s_.size()) {
                break;
            }
            string tmp = s_.substr(index, i);
            if (words.contains(tmp)) {
                if (i + index < s_.size()) {
                    tmp.push_back(' ');
                }
                cur += tmp;
                traverse(index + i);
                cur.erase(cur.size() - tmp.size());
            }
        }
    }
};