LeetCode 139 Word Break

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

概述

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;
    }
};

Links: leetcode-139-word-break