LeetCode 139 Word Break

标签: 动态规划问题 LeetCode 发布于:2022-03-02 16:33:42 编辑于:2022-03-02 16:33:42 浏览量:952

概述

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

动态规划

显然存在重复子问题。

每次函数调用 O(n),最多调用 O(n) 次,因此最终时间复杂度 O(n^2)。

class Solution {
public:
    set<string> c;
    vector<int> dp;
    bool wordBreak(string s, vector<string>& wordDict) {
        dp.resize(s.size(), -1);
        for (auto& w : wordDict) c.insert(w);
        return helper(s, 0);
    }
    
    bool helper(string& s, int k) {
        if (k == s.size()) return true;
        if (dp[k] != -1) return dp[k];
        string t;
        for (int i = k; i < s.size(); i ++) {
            t += s[i];
            if (c.count(t) != 0) {
                if (helper(s, i + 1)) return true;
            }
        }
        dp[k] = 0;
        return false;
    }
};

未经允许,禁止转载,本文源站链接:https://iamazing.cn/