us0 2020-06-25
给定一个非空字符串 s 和一个包含非空单词列表的字典 wordDict,判定 s 是否可以被空格拆分为一个或多个在字典中出现的单词。
说明:
示例:
输入: s = "leetcode", wordDict = ["leet", "code"] 输出: true 解释: 返回 true 因为 "leetcode" 可以被拆分成 "leet code"。 输入: s = "applepenapple", wordDict = ["apple", "pen"] 输出: true 解释: 返回 true 因为 "applepenapple" 可以被拆分成 "apple pen apple"。 ? 注意你可以重复使用字典中的单词。 输入: s = "catsandog", wordDict = ["cats", "dog", "sand", "and", "cat"] 输出: false
题目链接: https://leetcode-cn.com/problems/word-break/
使用动态规划来做。
s = "leetcode", wordDict = ["leet", "code"]
来说,dp[4]=true,因为 leet 在 wordDict 中。只要这 4 种情况有一种为 true,则说明 "leet" 能被拆分,所以 dp[4]=true。
代码如下:
class Solution { public: bool wordBreak(string s, vector<string>& wordDict) { unordered_set<string> lookup(wordDict.begin(), wordDict.end()); vector<bool> dp(s.size()+1, false); dp[0] = true; for(int i=1; i<=s.size(); i++){ for(int j=i-1; j>=0; j--){ dp[i] = dp[j] && (lookup.count(s.substr(j, i-j))!=0); if(dp[i]) break; } } return dp[s.size()]; } };
使用回溯来做。代码如下:
class Solution { bool ans = false; public: bool wordBreak(string s, vector<string>& wordDict) { int start = 0; unordered_set<string> lookup(wordDict.begin(), wordDict.end()); dfs(s, start, lookup); return ans; } void dfs(string s, int start, unordered_set<string> lookup){ if(start>=s.size()){ ans = true; return; } if(ans) return; for(int i=start+1; i<=s.size(); i++){ // 注意是 i<=s.size(),不是 i<s.size() if(lookup.count(s.substr(start, i-start))>0){ dfs(s, i, lookup); } } } };
备忘录算法。我们使用一个备忘录unordered_map<string, bool> memo
对思路 2 进行改进,也就是记录下那些不成功的子串分割,如果遇到之前出现的子串并有不成功的记录就不用往下递归了。代码如下:
class Solution { bool ans = false; public: bool wordBreak(string s, vector<string>& wordDict) { int start = 0; unordered_set<string> lookup(wordDict.begin(), wordDict.end()); unordered_map<string, bool> memo; // 备忘录 dfs(s, start, lookup, memo); return ans; } void dfs(string s, int start, unordered_set<string> lookup, unordered_map<string, bool>& memo){ if(start>=s.size()){ ans = true; return; } if(ans) return; for(int i=start+1; i<=s.size(); i++){ // 注意是 i<=s.size(),不是 i<s.size() string sub = s.substr(start, i-start); if(lookup.count(sub)>0){ if(memo.count(sub)==0 || memo[sub]!=false) dfs(s, i, lookup, memo); } memo[sub] = false; // 这样分割不行,记录下来不成功的子串 } } };
动态规划有时被称为递归的相反的技术。动态规划方案通常使用一个数组来建立一张表,用于存放被分解成众多子问题的解。当算法执行完毕,最终的解法将会在这个表中找到。今天我们先从我们最熟的斐波那契数列数列开始。
#include <iostream> #include <algorithm> #include <cstring> #include <cstdio&am