algo-aha

分割就是从一端尝试切下一段

将字符串分割成单词表中的单词

• https://leetcode.com/problems/word-break/

bool wordBreak(string s, vector<string>& wordDict) {
    // 设dp[i]表示s[i..]可分割成一个或多个单词，
    // dp[i] = any{ dp[j] && isWord(s[i..j-1]) }，0<=i<j<=N
    // 初始dp[N]=true
    unordered_set<string> dict;
    for (auto &s : wordDict)
        dict.insert(s);

    const int N = s.size();
    vector<bool> dp(N + 1, false);
    dp[N] = true;
    for (int i = N - 1; i >= 0; i--) {
        for (int j = i + 1; j <= N && !dp[i]; j++) {
            dp[i] = dp[j] && dict.count(s.substr(i, j - i));
        }
    }
    return dp[0];
}

类似：单词列表中有哪些单词能由多个短单词拼成

• https://leetcode.com/problems/concatenated-words/

变成找哪些长单词能分割成多个短单词。