161、【动态规划】leetcode ——139. 单词拆分:回溯法+动态规划(C++版本)
2023-09-11 14:20:01 时间
题目描述
原题链接:139. 单词拆分
解题思路
核心思路是采用Hash表的方式,存储wordDict
。每次采取切分一段字符串,然后在Hash表中匹配,看是否可在表中匹配到对应字符串。
(1)回溯法
class Solution {
private:
bool backtracking (const string& s, const 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() && backtracking(s, wordSet, i + 1)) {
return true;
}
}
return false;
}
public:
bool wordBreak(string s, vector<string>& wordDict) {
unordered_set<string> wordSet(wordDict.begin(), wordDict.end());
return backtracking(s, wordSet, 0);
}
};
此方式会超时。
(2)动态规划
- 动态规划五步曲:
(1)dp[j]数组含义: dp[j] == true
时,s中从0 ~ j - 1可以由wordDict
所组成。背包为字符串s,物品为字典单词。
(2)递推公式: 当在s中下标为[i-1, j]时,有对应的单词在wordDict中并且前i-1个字符可被wordDcit组成时, 让dp[j] = true。
(3)dp数组初始化: 为了便于计算让dp[j] = true。
(4)遍历顺序: 因为需要考虑顺序问题,例如appleandapple
,设apple
为1,and
为2,则应该得到为121才合法,如果得到的为112应不合法,不为我们的把目标。因此,这是一个考虑顺序的排列问题,应该先背包再物品。
(5)举例:
class Solution {
public:
bool wordBreak(string s, vector<string>& wordDict) {
int m = s.size();
unordered_set<string> record(wordDict.begin(), wordDict.end());
vector<bool> dp(m, false);
dp[0] = true;
for(int j = 1; j <= m; j++) { // 先遍历背包
for(int i = 1; i <= j; i++) { // 再遍历物品
string str = s.substr(i - 1, j - i + 1); // 从i-1处开始截取,截取字符串长为j-i+1的字符
// 查找str是否在单词表中,同时也要求str之前的字符串也可由单词表组成
if(record.find(str) != record.end() && dp[i - 1] == true) {
dp[j] = true;
}
}
}
return dp[m];
}
};
参考文章:139. 单词拆分
相关文章
- 托管C++线程锁实现 c++11线程池
- 编译器是C写的,包括一点C++,editor和debugger是C++写的(最早的16位编译器是纯汇编写的)
- 203、【栈与队列】leetcode ——剑指 Offer II 040. 矩阵中最大的矩形 / 85. 最大矩形:暴力+单调栈(C++/Pyhont版本)
- 192、【动态规划】leetcode ——64. 最小路径和:回溯法+动态规划(C++版本)
- 178、【数组/动态规划】leetcode ——392. 判断子序列:双指针+动态规划(C++版本)
- 176、【动态规划】leetcode ——1143. 最长公共子序列(C++版本)
- 170、【动态规划】leetcode ——188. 买卖股票的最佳时机 IV:二维数组+一维数组 (C++版本)
- 169、【动态规划】leetcode ——123. 买卖股票的最佳时机 III:二维数组+一维数组 (C++版本)
- 154、【动态规划】leetcode ——494. 目标和:回溯法+动态规划(C++版本)
- 152、【动态规划】leetcode ——416. 分割等和子集:滚动数组+二维数组(C++版本)
- 149、【动态规划】leetcode ——343. 整数拆分(C++版本)
- 148、【动态规划】leetcode ——63. 不同路径 II:递归法+迭代法(C++版本)
- 134、【贪心算法】leetcode ——134. 加油站(贪心策略)(C++版本)
- 119、【回溯算法】leetcode ——131. 分割回文串:分割问题(C++版本)
- 106、【树与二叉树】leetcode ——501. 二叉搜索树中的众数:双指针法+哈希表法(C++版本)
- 71、【哈希表】leetcode——350. 两个数组的交集 II(C++版本)
- 69、【哈希表】leetcode——202. 快乐数(C++版本)