LeetCode 139. 单词拆分

leetcode acwing

动态规划

算法1 \(O(n^3)\)

时间复杂度

因为substr()时间复杂度为\(O(n)\)，动态规划需要\(O(n^2)\)，所以整体时间复杂度为\(O(n^3)\)

空间复杂度

\(O(n^2)\)

C++ 代码

class Solution {
public:
    bool wordBreak(string s, vector<string>& wordDict) {
        unordered_set<string> dict(wordDict.begin(), wordDict.end());
        vector<bool> f(s.size() + 1, false);
        // 当s[1~i]能在wordDict中找到，dp[i]是合法的，为了保证结果合法，f[0] = true;
        f[0] = true;

        for (int i = 1; i <= s.size(); i ++)
        {
            for (int j = i; j >= 0; j --)
            {
                if (f[j] && (dict.find(s.substr(j, i - j)) != dict.end()))
                {
                    f[i] = true;
                    break;
                }
            }
        }

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

算法2

我们可以使用字符串哈希来代替原来程序中dict.find(s.substr(j, i - j)) != dict.end()这一段，字符串哈希使用\(O(1)\)的时间复杂度。

C++ 代码

class Solution {
public:
    bool wordBreak(string s, vector<string>& wordDict) {
        const int P = 131;
        typedef unsigned long long ULL;
        unordered_set<ULL> dict;

        for (auto word : wordDict)
        {
            ULL h = 0;
            for (auto c : word) h = h * P + c;
            dict.insert(h);
        }

        vector<bool> f(s.size() + 1, false);
        // 当s[1~i]能在wordDict中找到，dp[i]是合法的，为了保证结果合法，f[0] = true;
        f[0] = true;
        s = ' ' + s;
        // 和上面不一样，这里的i是一个分界点，左边的部分是已经匹配完成的部分f[i]，右边的部分则是待查找的字符串s[i + 1 ~ n];
        for (int i = 0; i < s.size(); i ++)
        {
            if (f[i])
            {
                ULL h = 0;
                for (int j = i + 1; j <= s.size(); j ++)
                {
                    h = h * P + s[j];
                    if (dict.count(h)) f[j] = true;
                }
            }
        }

        return f[s.size() - 1];
    }
};