// 错误的遍历顺序
class Solution {
public:
bool wordBreak(string s, vector<string>& wordDict) {
unordered_set<string> wordSet(wordDict.begin(), wordDict.end());
vector<bool> dp(s.size() + 1, false);
dp[0] = true;
for (int j = 0; j < wordDict.size(); j++) { // 物品
cout << endl << "******************" << endl;
for (int i = wordDict[j].size(); i <= s.size(); i++) { // 背包
string word = s.substr(i - wordDict[j].size(), wordDict[j].size());
cout << i - wordDict[j].size() << " " << word<< " " <<wordDict[j].size() << endl ;
if ( word == wordDict[j] && dp[i - wordDict[j].size()]) {
dp[i] = true;
cout << "true" << " " << i << " " << dp[i] << " " ;
}
//for (int k = 0; k <= s.size(); k++) cout << dp[k] << " "; //这里打印 dp数组的情况
cout << endl;
}
}
return dp[s.size()];
}
};
输出:
0 apple 5
true 5 1
1 pplep 5
2 plepe 5
3 lepen 5
4 epena 5
5 penap 5
6 enapp 5
7 nappl 5
8 apple 5
0 app 3
1 ppl 3
2 ple 3
3 lep 3
4 epe 3
5 pen 3
true 8 1
6 ena 3
7 nap 3
8 app 3
9 ppl 3
10 ple 3