题目

算法面试题汇总 - LeetBook - 力扣（LeetCode）全球极客挚爱的技术成长平台
https://leetcode-cn.com/leetbook/read/top-interview-questions/xa503c/

给定一个非空字符串 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作者：力扣 (LeetCode)
链接：https://leetcode-cn.com/leetbook/read/top-interview-questions/xa503c/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

题解

• 为了方便找到对应的字符串，使用set来当作字典存储wordDict
• 定义dp[i]表示字符串 ss前 i 个字符组成的字符串 s[0…i-1]是否能被空格拆分成若干个字典中出现的单词。
• 容易得到dp[i] = dp[j]&&wordDictSet.find(s.substr(j,i-j))，即判断前i的字符串是否能够拆分等价于判断前j的字符串是否能被拆分，且（i，j）的字符串是否是一个单词

class Solution {
public:bool wordBreak(string s, vector<string>& wordDict) {//为了方便找到对应的字符串，使用set来当作字典存储wordDictunordered_set<string> wordDictSet;for(auto word:wordDict){//将word添加进wordDictSetwordDictSet.insert(word);}//提前设置vector的大小，可以避免vector的扩容时的复制操作vector<bool> dp(s.size()+1);//初始化默认为0，即falsedp[0]=true;for(int i=1;i<=s.size();++i){for(int j=0;j<i;++j){if(dp[j]&&wordDictSet.find(s.substr(j,i-j))!=wordDictSet.end()){dp[i]=true;break;}}}return dp[s.size()];}
};