力扣139. 单词拆分

动态规划

• 思路：
  • 假设 dp[i] 为单词前 i 个字符能否被拆分的结果；
  • 假设最近的一个单词分割点 j，如果 dp[i] 能够被拆分，则 dp[j] 能被拆分，并且 s[j, i - 1] 在字典中；
  • 即状态转移方程： dp[i] = dp[j] && exist(s[j, i - 1])
  • 边界条件：空串可以被拆分， dp[0] = true；

class Solution {
public:
    bool wordBreak(string s, vector<string>& wordDict) {
        auto wordSet = std::unordered_set<std::string>();
        for (auto w:wordDict) {
            wordSet.insert(w);
        }

        auto dp = std::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] && wordSet.find(s.substr(j, i- j)) != wordSet.end()) {
                    dp[i] = true;
                    break;
                }
            }
        }

        return dp[s.size()];
    }
};