一、题目描述

示例 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

二、题解

通过回溯法进行暴力求解，时间复杂度 $O(n\times 2^n)$，空间复杂度 $O(n)$：

class Solution {
public:bool wordBreak(string s, vector<string> &word_dict) {unordered_set<string> word_set(word_dict.begin(), word_dict.end());return backtracking(s, word_set, 0);}private:bool backtracking(string &s, unordered_set<string> &word_set, int begin_index) {if (begin_index == s.size()) {return true;}for (int i = begin_index; i < s.size(); i++) {string temp = s.substr(begin_index, i - begin_index + 1);if (word_set.find(temp) != word_set.end()) {/* temp在字典中存在 */if (backtracking(s, word_set, i + 1)) {/* 拼接成功 */return true;}}}return false;}
};

上述方法在递归的过程中有很多重复计算，可以使用数组保存一下递归过程中计算的结果，虽然时间复杂度和空间复杂度没有改变，但是进行了大量剪枝，从而实现了优化。

通过回溯法进行记忆化递归求解，时间复杂度 $O(n\times 2^n)$，空间复杂度 $O(n)$：

class Solution {
public:bool wordBreak(string s, vector<string> &word_dict) {unordered_set<string> word_set(word_dict.begin(), word_dict.end());vector<bool> valid_tag(s.size(), true); // true表示初始值，false表示从当前下标开始无法完成拼接return backtracking(s, word_set, valid_tag, 0);}private:bool backtracking(string &s, unordered_set<string> &word_set, vector<bool> &valid_tag, int begin_index) {if (begin_index == s.size()) {return true;}/* 之前已经处理过从begin_index开始的拼接了，并且最终无法完成拼接 */if(!valid_tag.at(begin_index)) {return false;}for (int i = begin_index; i < s.size(); i++) {string temp = s.substr(begin_index, i - begin_index + 1);if (word_set.find(temp) != word_set.end()) {/* temp在字典中存在 */if (backtracking(s, word_set, valid_tag, i + 1)) {/* 拼接成功 */return true;}}}/* 从begin_index开始无法完成拼接 */valid_tag.at(begin_index) = false;return false;}
};

通过动态规划求解，由于二层循环里面对word_set的 find() 操作本质也是遍历，因此时间复杂度 $O(n^3)$，空间复杂度 $O(n)$：

class Solution {
public:bool wordBreak(string s, vector<string> &wordDict) {unordered_set<string> word_set(wordDict.begin(), wordDict.end());vector<bool> dp(s.size(), false); // dp[i]为true表示字符串s[0:i]可以被成功拼接/* 根据s.at(0)能否被拼接初始化动态规划数组 */if (word_set.find(s.substr(0, 1)) != word_set.end()) {dp.at(0) = true;}/* 从左向右递推 */for (int i = 1; i < s.size(); i++) {/* 如果s[0:i]本身就在字典中，直接continue */if (word_set.find(s.substr(0, i + 1)) != word_set.end()) {dp.at(i) = true;continue;}/* 依次判断s[0:j-1]和s[j:i]的状态 */for (int j = 1; j <= i; j++) {if (word_set.find(s.substr(j, i - j + 1)) != word_set.end() && dp.at(j - 1)) {dp.at(i) = true;continue;}}}return dp.at(dp.size() - 1);}
};