网站建设服务亿企网络,wordpress在线安装,深圳网站建设工作室,惠州的企业网站建设139. 单词拆分 (求排列方法)
题目链接#x1f525;#x1f525; 给定一个非空字符串 s 和一个包含非空单词的列表 wordDict#xff0c;判定 s 是否可以被空格拆分为一个或多个在字典中出现的单词。
说明#xff1a; 拆分时可以重复使用字典中的单词。 你可以假设字典中没…139. 单词拆分 (求排列方法)
题目链接 给定一个非空字符串 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
回溯思路分析
之前讲解回溯法专题的时候讲过的一道题目回溯算法分割回文串就是枚举字符串的所有分割情况。 本道是枚举分割所有字符串判断是否在字典里出现过。 回溯法C代码(会超时)
class Solution {
private:bool backtracking (const string s, const unordered_setstring 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() backtracking(s, wordSet, i 1)) {return true;}}return false;}
public:bool wordBreak(string s, vectorstring wordDict) {unordered_setstring wordSet(wordDict.begin(), wordDict.end());return backtracking(s, wordSet, 0);}
};递归的过程中有很多重复计算可以使用数组保存一下递归过程中计算的结果。
这个叫做记忆化递归这种方法我们之前已经提过很多次了。
使用memory数组保存每次计算的以startIndex起始的计算结果如果memory[startIndex]里已经被赋值了直接用memory[startIndex]的结果。
C代码如下
class Solution {
private:bool backtracking (const string s,const unordered_setstring wordSet,vectorbool memory,int startIndex) {if (startIndex s.size()) {return true;}// 如果memory[startIndex]不是初始值了直接使用memory[startIndex]的结果if (!memory[startIndex]) return memory[startIndex];for (int i startIndex; i s.size(); i) {string word s.substr(startIndex, i - startIndex 1);if (wordSet.find(word) ! wordSet.end() backtracking(s, wordSet, memory, i 1)) {return true;}}memory[startIndex] false; // 记录以startIndex开始的子串是不可以被拆分的return false;}
public:bool wordBreak(string s, vectorstring wordDict) {unordered_setstring wordSet(wordDict.begin(), wordDict.end());vectorbool memory(s.size(), 1); // -1 表示初始化状态return backtracking(s, wordSet, memory, 0);}
};背包思路分析
单词就是物品字符串s就是背包单词能否组成字符串s就是问物品能不能把背包装满。
拆分时可以重复使用字典中的单词说明就是一个完全背包
动规五部曲分析如下
确定dp数组以及下标的含义
dp[i] : 字符串长度为i的话dp[i]为true表示可以拆分为一个或多个在字典中出现的单词。
确定递推公式
如果确定dp[j] 是true且 [j, i] 这个区间的子串出现在字典里那么dp[i]一定是true。j i 。
所以递推公式是 if([j, i] 这个区间的子串出现在字典里 dp[j]是true) 那么 dp[i] true。
dp数组如何初始化
从递推公式中可以看出dp[i] 的状态依靠 dp[j]是否为true那么dp[0]就是递推的根基dp[0]一定要为true否则递推下去后面都都是false了。
那么dp[0]有没有意义呢
dp[0]表示如果字符串为空的话说明出现在字典里。
但题目中说了“给定一个非空字符串 s” 所以测试数据中不会出现i为0的情况那么dp[0]初始为true完全就是为了推导公式。
下标非0的dp[i]初始化为false只要没有被覆盖说明都是不可拆分为一个或多个在字典中出现的单词。
确定遍历顺序
题目中说是拆分为一个或多个在字典中出现的单词所以这是完全背包。
还要讨论两层for循环的前后顺序。
如果求组合数就是外层for循环遍历物品内层for遍历背包。 如果求排列数就是外层for遍历背包内层for循环遍历物品。
而本题其实我们求的是排列数为什么呢。 拿 s “applepenapple”, wordDict [“apple”, “pen”] 举例。
“apple”, “pen” 是物品那么我们要求 物品的组合一定是 “apple” “pen” “apple” 才能组成 “applepenapple”。
“apple” “apple” “pen” 或者 “pen” “apple” “apple” 是不可以的那么我们就是强调物品之间顺序。
所以说本题一定是 先遍历 背包再遍历物品。
如果先遍历物品再遍历背包
class Solution {
public:bool wordBreak(string s, vectorstring wordDict) {unordered_setstring wordSet(wordDict.begin(), wordDict.end());vectorbool dp(s.size() 1, false);dp[0] true;for (int j 0; j wordDict.size(); j) { // 物品for (int i wordDict[j].size(); i s.size(); i) { // 背包string word s.substr(i - wordDict[j].size(), wordDict[j].size());// cout word endl;if ( word wordDict[j] dp[i - wordDict[j].size()]) {dp[i] true;}// for (int k 0; k s.size(); k) cout dp[k] ; //这里打印 dp数组的情况 // cout endl;}}return dp[s.size()];}
};使用用例s “applepenapple”, wordDict [“apple”, “pen”]对应的dp数组状态如下 最后dp[s.size()] 0 即 dp[13] 0 而不是1因为先用 “apple” 去遍历的时候dp[8]并没有被赋值为1 还没用pen所以 dp[13]也不能变成1。
除非是先用 “apple” 遍历一遍再用 “pen” 遍历此时 dp[8]已经是1最后再用 “apple” 去遍历dp[13]才能是1。
举例推导dp[i]
代码实现
class Solution {
public:bool wordBreak(string s, vectorstring wordDict) {setstring dict(wordDict.begin(),wordDict.end());coutendl;vectorbool dp(s.size()1,false);dp[0]true;for(int j0;js.size();j){ // 遍历背包for(int i0;ij;i){ // 遍历物品if(dict.find(s.substr(i,j-i))!dict.end()dp[i]!false){//substr(起始位置截取的个数)dp[j]true;}}}return dp[s.size()];}
};思考总结
再理解一下这里为什么是排列不是组合。
