139題單詞拆分
鏈接: link
#include<iostream>
#include<sstream>
#include<string>
#include<vector>
#include<algorithm>
#include<unordered_set>
using namespace std;int main() {// 實現輸入第一行為s字符串。// 第二行為wordDict，用逗號隔開。string s;getline(cin, s);string line;vector<string> wordDict;getline(cin, line);istringstream iss(line);string single;while (getline(iss, single, ',')){wordDict.push_back(single);}// 函數處理階段。// 利用動態規劃處理// 首先定義dp數組vector<bool> dp(s.size()+1, false);// 把vector轉化為setunordered_set<string> dictSet(wordDict.begin(), wordDict.end());// 初始化數組dp[0] = true;// 開始遞推，因為字符串中單詞有順序，因此需要先遍歷背包for(int i = 1; i <= s.size(); i++){// 要注意j一定是小于i的。for(int j = 0; j < i; j++){string su_s = s.substr(j, i-j); // 截取從j開始到i之間大小的字符串if(dictSet.find(su_s) != dictSet.end() && dp[j]){dp[i] = true;}}}cout<<"str can finded!"<< dp[s.size()];// cout<<"s :"<<s<<endl;// //cout<<"詞典是:"<<endl;// for(auto c: wordDict){// cout<< c<<" ";// }// cout<<endl;return 0;
}
)
