给定一个非空字符串 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方法一：递归+记忆数组
class Solution { public: bool wordBreak(string s, vector<string>& wordDict) { unordered_set<string> wordSet(wordDict.begin(), wordDict.end()); vector<int> memo(s.size(), -1); return check(s, wordSet, 0, memo); } bool check(string s, unordered_set<string>& wordSet, int start, vector<int>& memo) { if (start >= s.size()) return true; if (memo[start] != -1) return memo[start]; for (int i = start + 1; i <= s.size(); ++i) { if (wordSet.count(s.substr(start, i - start)) && check(s, wordSet, i, memo)) { return memo[start] = 1; } } return memo[start] = 0; } };
方法二：动态规划
class Solution { public: bool wordBreak(string s, vector<string>& wordDict) { unordered_set<string> wordSet(wordDict.begin(), wordDict.end()); vector<bool> dp(s.size() + 1); dp[0] = true; for (int i = 0; i < dp.size(); ++i) { for (int j = 0; j < i; ++j) { if (dp[j] && wordSet.count(s.substr(j, i - j))) { dp[i] = true; break; } } } return dp.back(); } };
