Open GH1995 opened 5 years ago
dp[i]
表示范围[0, i)
内的子串是否可以拆分,注意这里dp
数组的长度比s
串的长度大1
,是因为我们要handle空串的情况,我们初始化dp[0]
为true
,然后开始遍历
if (dp[j] && wordSet.find(s.substr(j, i - j)) != wordSet.end()) {
dp[i] = true;
break;
}
定义dp
数组跟找出状态转移方程,先来看dp
数组的定义,这里我们就用一个一维的dp
数组,其中dp[i]
表示范围[0, i)
内的子串是否可以拆分,注意这里dp
数组的长度比s
串的长度大1,是因为我们要handle空串的情况,我们初始化dp[0]
为true
,然后开始遍历。注意这里我们需要两个for
循环来遍历,因为此时已经没有递归函数了,所以我们必须要遍历所有的子串,我们用j
把[0, i)
范围内的子串分为了两部分,[0, j)
和 [j, i)
,其中范围 [0, j)
就是dp[j]
,范围 [j, i)
就是s.substr(j, i-j)
,其中dp[j]
是之前的状态,我们已经算出来了,可以直接取,只需要在字典中查找s.substr(j, i-j)
是否存在了,如果二者均为true
,将dp[i]
赋为true
,并且break
掉,此时就不需要再用j
去分[0, i)
范围了,因为[0, i)
范围已经可以拆分了。最终我们返回dp
数组的最后一个值,就是整个数组是否可以拆分的布尔值了
class Solution {
public:
bool wordBreak(string s, vector<string>& wordDict) {
unordered_set<string> wordSet(wordDict.begin(), wordDict.end());
deque<bool> dp(s.size() + 1);
dp[0] = true;
for (int i = 0; i < dp.size(); ++i)
for (int j = 0; j < i; ++j)
if (dp[j] && wordSet.find(s.substr(j, i - j)) != wordSet.end()) {
dp[i] = true;
break;
}
return dp.back();
}
};
139. Word Break
Difficulty: Medium
Given a non-empty string s and a dictionary wordDict containing a list of non-empty words, determine if s can be segmented into a space-separated sequence of one or more dictionary words.
Note:
Example 1:
Example 2:
Example 3: