动态规划：单词拆分问题详解

1. 单词拆分

139. 单词拆分 - LeetCode

2. 算法原理

状态表示： 以某一个位置为结尾。dp[i] 表示在 [0, i] 区间里的字符串，能否被字典中的单词拼接而成。如果可以拼接则存储 true，否则为 false。

状态转移方程： 根据最后一个位置来划分问题。最后一个位置可能是由最后一个字符、最后两个字符...或整个字符串构成最后一个单词。 将区间划分为两部分：前面的部分能够拼接且后面的部分在字典中，则整个字符串可拼接。 设 j 表示最后一个单词起始位置的下标 (0 < j <= i)。 dp[i] 分为两种情况：

1. dp[j-1] == true && s(j~i) 是否在字典中
2. false

初始化： 需要加上一个虚拟节点，防止越界。dp[0] = true，表示空字符串可以拼接。

填表顺序： 从左往右。

返回值： 题目要求 + 状态表示，即 dp[n]。

3. 代码

class Solution {
public:
    bool wordBreak(string s, vector<string>& wordDict) {
        unordered_set<string> hash;
        for (const auto& word : wordDict) hash.insert(word);
        int n = s.size();
        vector<bool> dp(n + 1, false);
        dp[0] = true;
        for (int i = 1; i <= n; ++i) {
            for (int j = 1; j <= i; ++j) {
                if (dp[j - 1] && hash.count(s.substr(j - 1, i - j + 1))) {
                    dp[i] = true;
                    break;
                }
            }
        }
        return dp[n];
    }
};