【动态规划-7】139.单词拆分

题目描述给你一个字符串s和一个字符串列表wordDict作为字典。如果可以利用字典中出现的一个或多个单词拼接出s则返回true。注意不要求字典中出现的单词全部都使用并且字典中的单词可以重复使用。示例 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解题思路方法一动态规划核心思路状态定义dp[i] 字符串s的前i个字符能否由字典中的单词拼接而成。状态转移对于每个位置i枚举j从0到i-1如果dp[j] true且s[j..i-1]在字典中则dp[i] truedp[i] dp[j] wordDict.count(s.substr(j, i-j))初始化dp[0] true空字符串可以被拼接具体过程示例s leetcode, wordDict [leet, code]dp[0] true i1: 检查 s[0..0]l → 不在字典 → dp[1]false i2: 检查 s[0..1]le → 不在字典 → dp[2]false i3: 检查 s[0..2]lee → 不在字典 → dp[3]false i4: 检查 s[0..3]leet → 在字典dp[0]true → dp[4]true i5: 检查 s[0..4]leetc → 不在 检查 s[4..4]c → 不在 → dp[5]false i6: 检查 s[4..5]co → 不在 → dp[6]false i7: 检查 s[4..6]cod → 不在 → dp[7]false i8: 检查 s[4..7]code → 在字典dp[4]true → dp[8]true ✅代码实现class Solution { public: bool wordBreak(string s, vectorstring wordDict) { unordered_setstring dict(wordDict.begin(), wordDict.end()); int n s.size(); vectorbool dp(n 1, false); dp[0] true; for (int i 1; i n; i) { for (int j 0; j i; j) { if (dp[j] dict.count(s.substr(j, i - j))) { dp[i] true; break; } } } return dp[n]; } };复杂度分析设n是字符串长度m是字典大小。维度复杂度说明时间复杂度O(n² × L)双重循环 子串查找L 是子串长度空间复杂度O(n)dp 数组 哈希表更精确子串s.substr(j, i-j)创建需要 O(L) 时间所以是 O(n² × L)。关键细节1. 为什么dp[0] true空字符串可以被拼接什么都不选是递推的起点。2. 为什么用unordered_set字典需要频繁查找哈希表查找 O(1)比遍历数组快。3. 为什么break一旦dp[i] true不需要继续枚举j提前结束内层循环。4. 和「单词拆分 II」的区别题目区别139. 单词拆分判断能否拆分140. 单词拆分 II返回所有拆分方案方法二记忆化搜索DFS 备忘录代码实现class Solution { public: bool wordBreak(string s, vectorstring wordDict) { unordered_setstring dict(wordDict.begin(), wordDict.end()); unordered_mapint, bool memo; return dfs(s, dict, 0, memo); } private: bool dfs(string s, unordered_setstring dict, int start, unordered_mapint, bool memo) { if (start s.size()) return true; if (memo.count(start)) return memo[start]; for (int end start 1; end s.size(); end) { string word s.substr(start, end - start); if (dict.count(word) dfs(s, dict, end, memo)) { memo[start] true; return true; } } memo[start] false; return false; } };复杂度时间 O(n² × L)空间 O(n)方法三BFS代码实现class Solution { public: bool wordBreak(string s, vectorstring wordDict) { unordered_setstring dict(wordDict.begin(), wordDict.end()); int n s.size(); vectorbool visited(n, false); queueint q; q.push(0); while (!q.empty()) { int start q.front(); q.pop(); if (visited[start]) continue; visited[start] true; for (int end start 1; end n; end) { if (dict.count(s.substr(start, end - start))) { if (end n) return true; q.push(end); } } } return false; } };复杂度时间 O(n² × L)空间 O(n)三种方法对比方法时间复杂度空间复杂度推荐度动态规划O(n² × L)O(n)⭐⭐⭐⭐⭐记忆化搜索O(n² × L)O(n)⭐⭐⭐⭐BFSO(n² × L)O(n)⭐⭐⭐总结要点说明核心思想dp[i]表示前 i 个字符能否被拼接状态转移dp[i] dp[j] s[j..i-1] 在字典中初始化dp[0] true时间复杂度O(n² × L)空间复杂度O(n)