确定代码的运行次

Question

我今天写了下面的dp代码，它工作得很好，因为它提交了一些分数（here is the problem）。但是我无法确定我的代码的运行时间。我觉得它 O(n^2 * log D) 但我无法证明它。

class Solution {
public:
    unordered_map<string, bool> m;
    bool wordBreak(string s, unordered_set<string>& wordDict) {
        int n = s.length();
        string t = "";
        for(int i=0;i<n;i++){
            t += s.at(i);
            //cout << t << endl;
            if(wordDict.find(t) != wordDict.end()){
                m[t] = true;
                string x = "";
                for(int j=i+1;j<n;j++){
                    x += s.at(j);
                }
                if(x == ""){
                    return true;
                }
                if(m.find(x) != m.end()){
                    if(m[x] == true){
                        return true;
                    }else{
                        continue;
                    }
                }else{
                    if(wordBreak(x, wordDict)){
                        m[x] = true;
                        return true;
                    }else{
                        //cout << x << endl;
                        m[x] = false;
                        continue;
                    }
                }
            }else{
                //m[t] = false;
            }
        }
        return false;
    }
};

Answer 1

首先我会改写如下（未经测试）：

class Solution {
public:
    unordered_map<string, bool> m;
    bool wordBreak(string s, unordered_set<string>& wordDict) 
    {
        while (!s.empty())
        {
        int n = s.size() ;
        for(int i=0;i<n;i++){
            //cout << t << endl;
            if(wordDict.find(s.substr(0, i)) != wordDict.end()){
                m[t] = true;
                s = s.substr(i) ;
                break ;
        }
        return !m.empty();
    }
};

基本思路是，一旦找到匹配项，就可以从字符串中删除匹配部分。那么我会说它是 n * logD。毕竟，您只在 for 循环中传递了一次。假设您在 m < n 处找到一个匹配项，那么您会得到一个新的循环 (n-m)。

Answer 2

它似乎有 O(n*n) 复杂性。你使用记忆，算法的每一步都会在 m 中产生至少 1 个新值。任何字符串中都有 n*n/2 个子字符串，因此在最坏的情况下，您将找到具有 n*n/2 个段落的整个字符串的解决方案。

PS：考虑 unordered_map 与 O(1) 一起使用。

编辑：

在您的情况下考虑 unordered_map 使用 O(n) 可能更合适。 m.find 需要为其参数计算哈希值，即字符串。如果你存储索引而不是字符串本身，它可能会工作得更快。

Answer 3

我是这样解决的。

bool wordBreak(string s, unordered_set<string>& wordDict) {
    if (s.empty()) return true;

    vector<bool> dp(s.size(), false);
    for (int i = 0; i < dp.size(); ++i)
    {
        for (int j = i; j >= 0; --j)
        {
            if (wordDict.find(s.substr(j, i - j + 1)) != wordDict.end() &&
                (j == 0 || dp[j - 1]))
            {
                dp[i] = true;
                break;
            }
        }
    }

    return dp.back();
}

确定代码的运行次

Determine running time of the code

c++

dynamic-programming

asymptotic-complexity