49. 单词拆分

题目

解析

1. 从第一个到最后一个字母进行遍历，父循环循环变量(i)决定子串的右端
2. 其次，子循环循环变量(j)决定子串的左端
3. 然后，若是j左侧不可拆分，那么就跳过（因为左边无法拆分，即便右边可以拆分也没有意义）
4. 输出dpn

【释】：**dp** 负责记录 第n个之前（包括第n个）能否拆分

代码

#include <bits/stdc++.h>

using namespace std;

int main()
{
    string s;
    int n, nn;
    cin >> s >> nn;
    n = s.size();
    vector<bool> dp(n + 1, false);
    set<string> ss;
    for (int i = 0; i < nn; i++) {
        string t;
        cin >> t;
        ss.insert(t);
    }

    dp[0] = true;
    for (int i = 0; i <= n; i++) {
        for (int j = i; j > 0; j--) {
            if (!dp[j - 1])
                continue;
            if (ss.find(s.substr(j - 1, i - j + 1)) != ss.end()) {
                dp[i] = true;
                break;
            }
        }
    }

    cout << boolalpha << dp[n];
    return 0;
}