力扣139. 单词拆分

2023-12-13 04:28:31

动态规划

  • 思路:
    • 假设 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()];
    }
};

文章来源:https://blog.csdn.net/N_BenBird/article/details/134960841
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。