阅读目录
- 1. 题目
- 2. 解题思路
- 3. 代码实现
1. 题目
2. 解题思路
定义 d p [ i ] dp[i] dp[i] 表示 s [ 0 , i ] s[0, i] s[0,i] 是否可以被字典中出现的单词拼接，那么状态转移方程为：
d p [ i ] = t r u e ，如果存在任意 j ∈ [ 0 , i − 1 ] ， 满足 d p [ j ] = t r u e ，并且 s [ j + 1 , i ] ∈ w o r d D i c t dp[i] = true，如果存在任意\space j \in [0,i-1]，\\ 满足\space dp[j] =true， 并且 \space s[j+1, i] \in wordDict dp[i]=true，如果存在任意 j∈[0,i−1]，满足 dp[j]=true，并且 s[j+1,i]∈wordDict
也就是 s [ 0 , j ] s[0, j] s[0,j] 可以被字典中出现的单词拼接，并且 s [ j + 1 , i ] s[j+1, i] s[j+1,i] 存在于字典中，那么 s [ 0 , i ] s[0, i] s[0,i] 也可以被拼接。
同时，我们定义空字符串 d p [ − 1 ] = t r u e dp[-1]=true dp[−1]=true。
由于需要两层循环，所以时间复杂度为 O ( n 2 ) O(n^2) O(n2)，另外，我们需要一个哈希表来存储 w o r d D i c t wordDict wordDict，所以空间复杂度为 O ( n ) O(n) O(n)。
3. 代码实现
class Solution {
public:bool wordBreak(string s, vector<string>& wordDict) {vector<bool> dp(s.size(), false);unordered_map<string, bool> wordMap;for (int i = 0; i < wordDict.size(); ++i) {wordMap[wordDict[i]] = true;}for (int i = 0; i < s.size(); ++i) {for (int j = i-1; j >= -1; --j) {if (j != -1 && !dp[j]) {continue;}string sub_str = s.substr(j+1, i-j);if (wordMap.count(sub_str)) {dp[i] = true;break;}}}return dp.back();}
};
