1. 题目链接：139. 单词拆分
2. 题目描述：
给你一个字符串
s和一个字符串列表wordDict作为字典。请你判断是否可以利用字典中出现的单词拼接出s。**注意：**不要求字典中出现的单词全部都使用，并且字典中的单词可以重复使用。
示例 1：
输入: s = "leetcode", wordDict = ["leet", "code"] 输出: true 解释: 返回 true 因为 "leetcode" 可以由 "leet" 和 "code" 拼接成。示例 2：
输入: s = "applepenapple", wordDict = ["apple", "pen"] 输出: true 解释: 返回 true 因为 "applepenapple" 可以由 "apple" "pen" "apple" 拼接成。 注意，你可以重复使用字典中的单词。示例 3：
输入: s = "catsandog", wordDict = ["cats", "dog", "sand", "and", "cat"] 输出: false提示：
1 <= s.length <= 3001 <= wordDict.length <= 10001 <= wordDict[i].length <= 20s和wordDict[i]仅由小写英文字母组成wordDict中的所有字符串 互不相同
3. 解法（动态规划）：
3.1 算法思路：
1. 状态表示：
dp[i]表示： [0,i]区间内的字符串，能否被字典中的单词拼接而成
2. 状态转移方程：
对于 dp[i]，为了确定当前的字符串能否由字典里面的单词构成，根据最后一个单词的起始位置 j，我们可以将其分解为前后两部分：
- 前面一部分：
[0,j-1]区间的字符串 - 后面一部分：
[j,i]区间的字符串
其中前面部分我们可以在 dp[i-1]中找到答案，后面部分的字串可以在字典里面找到。
因此，我们可以得出一个结论：当我们在从 0~i枚举 j的时候，只要 dp[j-1]=true并且后面部分的字串 s.substr(j,i-j+1)能够在字典中找到，那么 dp[i]=true
3. 初始化：
可以在最前面加上一个辅助结点，帮助我们初始化，使用这种技巧注意两个点：
- 辅助结点里面的值要保证后续填表是正确的
- 下标的映射关系
在本题中，最前面加上一个格子，并且让 dp[0]=true，可以理解为空串能够拼接而成。其中为了方便处理下标的映射关系，我们可以将字符串前面加上一个占位符 s=' '+s，这样就没有下标的映射问题了，同时还能处理空串的情况
4. 填表顺序：
从左往右
5. 返回值：
返回 dp[n]位置的布尔值
哈希表优化的小细节：
在状态转移中，我们需要判断后面部分的子串是否在字典之中，因此会频繁的用到查询操作，为了节省效率我们可以提前把字典中的单词存入到哈希表中
3.2 C++算法代码：
class Solution {
public:
// 判断字符串s是否可以由wordDict中的单词拼接而成
bool wordBreak(string s, vector<string>& wordDict) {
// 将wordDict中的单词存入哈希集合中，方便后续查找
unordered_set<string> hash;
for(auto&s:wordDict) hash.insert(s);
int n=s.size();
// dp数组，dp[i]表示字符串s的前i个字符是否可以由wordDict中的单词拼接而成
vector<bool> dp(n+1);
dp[0]=true;
// 在字符串s前加上一个空格，方便后续处理
s=' '+s;
// 遍历字符串s的每个字符
for(int i=1;i<=n;i++)
{
// 从当前字符开始向前遍历，尝试所有可能的子串
for(int j=i;j>=1;j--)
{
// 如果前j-1个字符可以由wordDict中的单词拼接而成，且第j个字符到第i个字符组成的子串也在wordDict中
// 那么可以将整个字符串s的前i个字符由wordDict中的单词拼接而成
if(dp[j-1]&&hash.count(s.substr(j,i-j+1)))
{
dp[i]=true;
break;
}
}
}
// 返回结果，如果字符串s的所有字符都可以由wordDict中的单词拼接而成，则返回true，否则返回false
return dp[n];
}
};
