phpmysql做网站,昆明君创网络科技有限公司,网站组织管理建设,大连建立网站公司文档讲解#xff1a;单词拆分 139.单词拆分
题目链接#xff1a;https://leetcode.cn/problems/word-break/description/
思路#xff1a; 单词就是物品#xff0c;字符串s就是背包#xff0c;单词能否组成字符串s#xff0c;就是问物品能不能把背包装满。 拆分时可以重… 文档讲解单词拆分 139.单词拆分
题目链接https://leetcode.cn/problems/word-break/description/
思路 单词就是物品字符串s就是背包单词能否组成字符串s就是问物品能不能把背包装满。 拆分时可以重复使用字典中的单词说明就是一个完全背包 设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[i] 的状态依靠 dp[j]是否为true那么dp[0]就是递推的根基dp[0]一定要为true否则递推下去后面都都是false了。
核心代码
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 i 1; i s.size(); i) { // 遍历背包for (int j 0; j i; j) { // 遍历物品string word s.substr(j, i - j); //substr(起始位置截取的个数)if (wordSet.find(word) ! wordSet.end() dp[j]) {dp[i] true;}}}return dp[s.size()];}
};
今日总结 今日学习时长2h接着八股文。 这题是我专业面试一原题没想到又在这碰到了哈哈哈缘分。当时没用动态规划直接map开桶暴力解决了还记得当时面试官震撼到了哈哈哈。 接着论文idea头大。
