139. 单词拆分
2 min
题目
解法：动态规划
思路
核心思想是动态规划，定义 dp[i] 表示前 i 个字符能否被拼接。
正确性基于最优子结构：若 s[0
] 可被拼接，则必存在分割点 j，使得 s[0] 可被拼接且 s[j] 是字典单词；反之亦然。这保证了状态转移的完备性。- Step 1: 构建哈希集合存储字典，实现 O(1) 查找
- Step 2: 初始化 dp[0] = true，表示空字符串可拼接
- Step 3: 遍历每个位置 i，尝试所有分割点 j
- Step 4: 若 dp[j] 为 true 且子串 s[j] 在字典中，则设置 dp[i] = true
- Step 5: 返回 dp[n] 作为最终结果
复杂度
- 时间复杂度:
- 空间复杂度:
代码
class Solution {
public:
bool wordBreak(string s, vector<string>& wordDict) {
unordered_set<string> dict(wordDict.begin(), wordDict.end());
int n = s.size();
vector<bool> 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];
}
};