139. 单词拆分
https://leetcode.cn/problems/word-break/description/
给你一个字符串s和一个字符串列表wordDict作为字典。如果可以利用字典中出现的一个或多个单词拼接出s则返回true。注意：不要求字典中出现的单词全部都使用，并且字典中的单词可以重复使用。
- 输入：s = "leetcode"，wordDict = ["leet", "code"]，输出：true，解释：返回true因为"leetcode"可以由"leet"和"code"拼接成。
- 输入：s = "applepenapple"，wordDict = ["apple", "pen"]，输出：true，解释：返回true因为"applepenapple"可以由"apple" "pen" "apple"拼接成。注意，你可以重复使用字典中的单词。
- 输入：s = "catsandog"：wordDict = ["cats", "dog", "sand", "and", "cat"]，输出：false。
提示：1 <= s.length <= 300，1 <= wordDict.length <= 1000，1 <= wordDict[i].length <= 20，s和wordDict[i]仅由小写英文字母组成，wordDict中的所有字符串互不相同。
我们用动态规划的思想来解决这个问题。
确定状态表示：根据经验和题目要求，我们用dp[i]表示：以i位置为结尾的子串，能否被字典中的单词拼接。
推导状态转移方程：如果以i位置为结尾的子串可以被字典中的单词拼接，那么一定分为前半部分和后半部分，后半部分是一个单词。我们用j遍历[0, i]的范围，如果有至少1个j同时满足：
- dp[j - 1] == true，即以j - 1位置为结尾的子串可以被拼接。
- s的下标范围在[j, i]的子串在字典中。
则dp[i] = true。如果没有1个j同时满足这2个条件，那么dp[i] = false。
但是由于j的范围是[0, i]，当j = 0时，j - 1 = -1，判断dp[j - 1]时会越界，我们需要处理一下。显然，当j = 0时，表示前半部分不存在，后半部分是子串的整体，此时只需判断条件2是否满足。
初始化：根据状态转移方程，填dp表时不存在越界问题，不需要初始化。
填表顺序：根据状态转移方程，显然应从左往右填表。
返回值：根据状态表示，应返回dp[n - 1]，其中n为字符串s的长度。
细节问题：dp表的规模和字符串s相同，均为1 x n。为了方便查找子串是否在字典中，可以先把字典中的所有字符串存储到哈希表中。
class Solution {
public:
bool wordBreak(string s, vector<string>& wordDict) {
int n = s.size();
unordered_set hash(wordDict.begin(), wordDict.end());
// 创建dp表
vector<bool> dp(n);
// 填表
for (int i = 0; i < n; i++) {
for (int j = i; j >= 0; j--) {
if ((j == 0 || dp[j - 1]) &&
hash.count(s.substr(j, i - j + 1))) {
dp[i] = true;
break;
}
}
}
return dp[n - 1];
}
};