给定一个非空字符串 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
解法一：
//时间复杂度O(n^2), 空间复杂度O(n)
class Solution {
public:
bool wordBreak(const string& s, const unordered_set<string>& us,
vector<int>& vec, int start) {
if(start == s.size()) return true;
if(vec[start] != -1) return vec[start];
for(int i = start + 1; i <= s.size(); i++) {
if(us.count(s.substr(start, i - start)) &&
wordBreak(s, us, vec, i)) {
vec[start] = 1;
return true;
}
}
vec[start] = 0;
return false;
}
bool wordBreak(string s, vector<string>& wordDict) {
unordered_set<string> us;
for(string& word : wordDict) us.insert(word);
vector<int> vec(s.size(), -1);
return wordBreak(s, us, vec, 0);
}
};//时间复杂度O(n^2), 空间复杂度O(n)
class Solution {
public:
bool wordBreak(string s, vector<string>& wordDict) {
unordered_set<string> us;
for(const string& word : wordDict) us.insert(word);
vector<bool> dp(s.size() + 1, false);
dp[0] = true;
for(int i = 1; i <= s.size(); i++) {
for(int j = 0; j < i; j++) {
if(dp[j] && us.count(s.substr(j, i - j))) {
dp[i] = true;
}
}
}
return dp[s.size()];
}
};解法一：
记忆优化递归。先考虑暴力搜索法，需要遍历每一个前缀，只有前缀包含在wordDict中才继续向下递归。但是暴力法效率太低，不能通过测试。
所以就将其n个后缀的结果存储在数组vec中，vec[i]==1说明s.substr(i)满足拆分要求，vec[i]==0说明不满足，vec[i]==-1说明未确定，此时需要递归向下进行。
递归树最深为n，所以空间复杂度为O(n)；时间复杂度暂时没想明白，求指导。
解法二：
动态规划。突破点同解法一，只不过解法二是从左向右走。假设设字符串s的某一前缀s.substr(0,j)（包括s[0]但不含s[j]）满足拆分要求，如果s的子串s.substr(j, i-j)出现在wordDict中，那么该前缀与该子串的组合s.substr(0,i)也满足拆分要求。所以可用长为n+1的数组dp来记录状态，其中dp[i]为真代表从0到i的前缀满足拆分要求。所以有如下递推关系：
if(dp[j] && us.count(s.substr(j, i - j))) dp[i] = true;
可以知道空串也算出现在wordDict中，即dp[0]为真。
通过从前向后递推，遍历所有i和j的位置，最终dp[s.size()]就是所求的答案。其余细节如上代码。
2019/12/18 19:18