题目
给定一个非空字符串 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 backtracing(string s,unordered_set<string>& wordSet,int startIndex){ if(startIndex>=s.size()) return true; for(int i=startIndex;i<s.size();i++){ string word=s.substr(startIndex,i-startIndex+1); if(wordSet.find(word)!=wordSet.end()&&backtracing(s,wordSet,i+1)){ return true; } } return false; } bool wordBreak(string s, vector<string>& wordDict) { unordered_set<string> wordSet(wordDict.begin(),wordDict.end()); return backtracing(s,wordSet,0); } };
剪枝后
class Solution { public: bool backtracing(string s,unordered_set<string>& wordSet,vector<int>& memory,int startIndex){ if(startIndex>=s.size()) return true; if (memory[startIndex] == 0) return false;//以startIndex开始的子串是不可以被拆分的，直接return for(int i=startIndex;i<s.size();i++){ string word=s.substr(startIndex,i-startIndex+1); if(wordSet.find(word)!=wordSet.end()&&backtracing(s,wordSet,memory,i+1)){ return true; } } memory[startIndex] = 0; // 记录以startIndex开始的子串是不可以被拆分的 return false; } bool wordBreak(string s, vector<string>& wordDict) { unordered_set<string> wordSet(wordDict.begin(),wordDict.end()); vector<int> memory(s.size(), -1); // -1 表示初始化状态 return backtracing(s,wordSet,memory,0); } };
方法二：动态规划
可以把字符串大小，看成背包容量
把每个字典中出现的单词看作物品
本题最终要求的是是否都出现过，所以对出现单词集合里的元素是组合还是排列，并不在意
那么本题使用求排列的方式，还是求组合的方式都可以。
初始dp[0]=True,出0外dp[i]=False
如果dp[i]=true,就代表容量为i的字串串s[0:i+1]可以装满，单词，反之则不可以
也就是说,要判断5到8的时候，5到8是一个单词，那么必定要求dp[4]=true可以拆分为一个或者以上的单词，这样才能使得dp[8]可以拆分。
class Solution { public: bool wordBreak(string s, vector<string>& wordDict) { unordered_set<string> wordSet(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=0;j<i;j++){//遍历物品 string word=s.substr(j,i-j); if(wordSet.find(word)!=wordSet.end()&&dp[j]){ dp[i]=true; } } } return dp[s.size()]; } };
java
class Solution { public boolean wordBreak(String s, List<String> wordDict) { Set<String> set=new HashSet<>(wordDict); boolean[] dp=new boolean[s.length()+1]; dp[0]=true; for(int i=1;i<=s.length();i++){ for(int j=0;j<i;j++){ String word=s.substring(j,i); if(set.contains(word)&&dp[j]){ dp[i]=true; } } } return dp[s.length()]; } }
方法三：字典树+记忆化dfs
这里的字典树用于保存字符串的作用其实是和哈希集合是一样的，只是用字典树进行保存。
后续用的记忆化dfs，本质上是和哈希集合是一样的，只不过用的是字典树的查找方式
c++
class Trie{ public: bool isEnd=false; vector<Trie*> next=vector<Trie*>(26,nullptr); }; class Solution { public: Trie* trie=new Trie(); vector<bool> failed; bool wordBreak(string s, vector<string>& wordDict) { for(string& word:wordDict){ insert(word); } failed=vector<bool>(s.size()+1,false);//记忆化，如果为true，说明从该索引开始（包括），匹配失败 return dfs(s,0); } bool dfs(string& word,int startIndex){ if(failed[startIndex]) return false;//记忆化过了，直接返回结果。 if(startIndex==word.size()) return true; Trie* node=trie; for(int i=startIndex;i<word.size();i++){ char c=word[i]; if(node->next[c-'a']) node=node->next[c-'a']; else return false; if(node->isEnd){ if(dfs(word,i+1)) return true; failed[i+1]=true;//记忆化：从这个字母开始匹配失败的 } } return false; } void insert(string& word){ Trie* node=trie; for(char c:word){ if(node->next[c-'a']==nullptr){ node->next[c-'a']=new Trie(); } node=node->next[c-'a']; } node->isEnd=true; } };
java
class Trie{ public boolean isEnd; Trie[] next; Trie(){ isEnd=false; next=new Trie[26]; } } class Solution { Trie trie; boolean[] failed; public boolean wordBreak(String s, List<String> wordDict) { trie=new Trie(); for(String word:wordDict){ insert(word); } failed=new boolean[s.length()+1]; return dfs(s,0); } void insert(String word){ Trie node=trie; for(char c:word.toCharArray()){ if(node.next[c-'a']==null){ node.next[c-'a']=new Trie(); } node=node.next[c-'a']; } node.isEnd=true; } boolean dfs(String word,int startIndex){ if(failed[startIndex]) return false; if(startIndex==word.length()) return true; Trie node=trie; for(int i=startIndex;i<word.length();i++){ char c=word.charAt(i); if(node.next[c-'a']!=null) node=node.next[c-'a']; else return false; if(node.isEnd){ if(dfs(word,i+1)) return true; failed[i+1]=true; } } return false; } }
