原题地址
https://leetcode.com/problems/word-break/description/
题意
给出一个string和一个string的vector，判断能否用vector里的string组成给定的string，vector里的string可重复用。
思路
dp2i表示给定string的前i个字符组成的子串能否被vector里的string组成，最后结果返回dp2[给定string长度]。
递推方程
dp2[i] = dp2[ i- length( wordDict[k] ) ] && helper(s.substr(…), wordDick[k])
helper用来判断是否能用dict里的某个string（重复多次）组成目标串的某个长度相等的子串。
代码
也是错了很多遍才打对的题。。
Solution {
public:
bool helper(string source, string word) {
if (source.size() % word.size() != 0) return false;
int fork = source.size() / word.size();
string a("");
for (int i = 0; i < fork; i++) {
a += word;
}
return a == source;
}
bool wordBreak(string s, vector<string>& wordDict) {
int n1 = s.size();
if (n1 == 0) return true;
int n2 = wordDict.size();
if (n2 == 0) return false;
bool dp[n1 + 1][n2];
bool dp2[n1 + 1];
dp2[0] = true;
for (int i = 0; i < n2; i++) {
dp[0][i] = true;
}
for (int i = 1; i <= n1; i++) {
dp2[i] = false;
for (int j = 0; j < n2; j++) {
int temp = i - wordDict[j].size();
if (temp >= 0) {
dp2[i] = (dp2[temp] && (helper(s.substr(temp, wordDict[j].size()), wordDict[j])));
}
if (dp2[i]) break;
}
}
for (int i = 1; i <= n1; i++) {
cout << dp2[i] << " ";
}
return dp2[n1];
}
};
坑点
原来在某些情况下，Run Code 和submit上去的运行结果会不一样的
leetcodeerr.png
参考了一下这里，也没有找到和我的代码相对应的情况。。后来发现dp2[0]忘记初始化为true了，改了之后就能AC了，但还是觉得很懵B，不知道为什么run code时结果正确。
