Code & Fun

第33天。

做了超级久。。。还是没做出来,我真是菜啊,明明已经想到了要用动态规划来做了。

今天的题目是:Word Break:

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. You may assume the dictionary does not contain duplicate words.

For example, given
s = “leetcode”,
dict = [“leet”, “code”].

Return true because “leetcode” can be segmented as “leet code”.

因为没做出来,所以只能讲别人的思路了。。。

首先这里是要用动态规划去做的,我们需要一个vector<bool> db来记录s.substr(0,i+1)的子串是否能用wordDict进行break,如果我们要求db[i]我们是否能利用db[0:i]的值呢,比如,如果0<= k < i,且db[k]==true,那么我们是不是只需要在wordDict中查找是否有s.substr(i,k-i)就可了呢:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
bool wordBreak(string s,vector<string> &wordDict) {
if(wordDict.size() == 0) return false;
vector<bool> dp(s.size() + 1,false);
dp[0] = true;
for(int i = 1;i <= s.size();i++) {
for(int j = i-1;j >= 0;j--) {
if (dp[j]) {
string word = s.substr(j,i-j);
if (find(wordDict.begin(),wordDict.end(),word) != wordDict.end()) {
dp[i] = true;
break;
}
}
}
}
return dp[s.size()];
}

因为是别人的思路,所以也没法复现思考的过程了,总结一下没做出来的原因吧。
虽然说算法课上刚讲了DP,当时他讲的时候我还觉得挺简单的,还以为自己已经会了,因为之前已经做过好几次DP的题目了,现在想想上课我就记得他吐槽了DP的恋爱观,什么总是找局部最优解巴拉巴拉的。
哎,这种东西还是要自己体会才行,恩,决定了,这几天刷会DP的题目先。


本文首发于Code & Fun