[C++知识库]单词拆分。

• ACM模式的输入输出是真的搞人

?

?C++代码参考：

?

#include<iostream>
#include<vector>
#include <string>
#include<unordered_set>
using namespace std;

//单词拆分验证
bool wordBreak(string s, vector<string>& wordDict) 
{
    auto wordDictSet = unordered_set <string>();
    for (auto word : wordDict) {
        wordDictSet.insert(word);
    }

    auto dp = vector <bool>(s.size() + 1);
    dp[0] = true;
    for (int i = 1; i <= s.size(); ++i) {
        for (int j = 0; j < i; ++j) {
            if (dp[j] && wordDictSet.find(s.substr(j, i - j)) != wordDictSet.end()) {
                dp[i] = true;
                break;
            }
        }
    }

    return dp[s.size()];
}

int main()
{
    int b;
    string s;
    vector<string> dictionary;
    //输入并存储字典
    while (cin >> s)
    {
        dictionary.push_back(s);
        if (cin.get() == '\n')
            break;
    }
    while (cin >> s)
    {
        int result = wordBreak(s, dictionary);
        if (result)
        {
            cout<<"匹配" <<endl;
        }
        else
        {
            cout << "不匹配" << endl;
        } 
    }
    return 0;
}