力扣题目链接：https://leetcode.cn/problems/word-break-ii/
给定一个字符串 s 和一个字符串字典 wordDict ，在字符串 s 中增加空格来构建一个句子，使得句子中所有的单词都在词典中。以任意顺序 返回所有这些可能的句子。
注意：词典中的同一个单词可能在分段中被重复使用多次。
示例 1：
输入:s = "catsanddog", wordDict = ["cat","cats","and","sand","dog"] 输出:["cats and dog","cat sand dog"]
示例 2：
输入:s = "pineapplepenapple", wordDict = ["apple","pen","applepen","pine","pineapple"] 输出:["pine apple pen apple","pineapple pen apple","pine applepen apple"] 解释: 注意你可以重复使用字典中的单词。
示例 3：
输入:s = "catsandog", wordDict = ["cats","dog","sand","and","cat"] 输出:[]
提示：
- 1 <= s.length <= 20
- 1 <= wordDict.length <= 1000
- 1 <= wordDict[i].length <= 10
- s 和 wordDict[i] 仅有小写英文字母组成
- wordDict 中所有字符串都 不同
待分割的字符串的最大长度为 20 20 20，而 20 × 2 20 = 20 , 971 , 520 20times 2^{20}=20,971,520 20×220=20,971,520，加上很多情况下很快就会break（除非专门造的卡数据的数据），因此能够在规定时间内完成运行。
如果说到状态压缩，这道题与131. 分割回文串解法十分类似。
与(https://leetcode.letmefly.xyz/2022/07/23/LeetCode 0131.分割回文串/)[https://leetcode.letmefly.xyz/2022/07/23/LeetCode%200131.%E5%88%86%E5%89%B2%E5%9B%9E%E6%96%87%E4%B8%B2/]解法相同，首先我们用 i i i枚举在哪个下标切割。
长度为 n n n的字符串一共有 n − 1 n-1 n−1个可以切割的地方。
之后用 j j j从 0 0 0到 n − 1 n-1 n−1，看这 n − 1 n-1 n−1个可切割位置到底哪个真正地进行了切割。然后把切割出来的子串与字典比对，看是否存在于字典中。若所有子串都存在于字典中，则用空格连接这种切割方式下的所有子串，并计入答案中。
- 时间复杂度 O ( n × 2 n ) O(ntimes 2^n) O(n×2n)，其中 n n n是字符串的长度。二进制状态压缩枚举的时间复杂度为 2 n 2^n 2n，对于某次枚举(切割方式)，需要判断这种切割方式是否每个子串都在字典中，时间复杂度 O ( n ) O(n) O(n)（哈希表时间复杂度可以视为O(1)）
- 空间复杂度 O ( m + n ) O(m + n) O(m+n)，其中 m m m是字典中的所有字符个数。二进制状态压缩相比于基于递归的状态压缩，优点是不需要递归（因此也就不需要消耗递归的空间），而答案不计入算法的复杂度，因此存放字典外的空间复杂度仅为单次枚举时候所需要的额外空间 O ( n ) O(n) O(n)
#define judge(thisWord)
if (!st.count(thisWord))
goto loop;
thisBreak.push_back(thisWord);
class Solution {
public:
vector wordBreak(string s, vector& wordDict) {
vector ans;
unordered_set st;
for (string& s : wordDict) {
st.insert(s);
}
int n = s.size() - 1;
for (int i = 0; i < (1 << n); i++) {
vector thisBreak;
string toInsert;
string thisWord;
int last = 0;
for (int j = 0; j < n; j++) {
if (i & (1 << j)) {
thisWord = s.substr(last, j - last + 1);
judge(thisWord);
last = j + 1;
}
}
thisWord = s.substr(last, s.size() - last);
judge(thisWord);
for (int i = 0; i < thisBreak.size(); i++) {
if (i)
toInsert += ' ';
toInsert += thisBreak[i];
}
ans.push_back(toInsert);
loop:;
}
return ans;
}
};
同步发文于CSDN，原创不易，转载请附上原文链接哦~
Tisfy：https://letmefly.blog.csdn.net/article/details/126016024
