Word Break

题目描述

Given a string s and a dictionary of words dict, determine if s can be break into a space-separated sequence of one or more dictionary words.

Example:

Given s = "lintcode", dict = ["lint", "code"]. Return true because "lintcode" can be break as "lint code".

题目链接

方法是：Hash + DP

• 先对每个字符串计算hash值，之后就可以用比较hash值来代替比较字符串。
• dp[i]表示下标从 i 开始知道字符串结尾是否可以拆分成字典中的单词。
• dp每一步转移的方法数实际上是 字典中长度不同的单词的个数。

time complexity：$$ O(n \times m) $$

here $$n$$ is the length of input string s, and $$m$$ is the number of distinct length of words in dict.

参考代码

class Solution {
public:
    /**
     * @param s: A string s
     * @param dict: A dictionary of words dict
     */

    typedef unsigned long long ull;


    ull get_hash(const string &s) {
        ull h = 0;
        for (const char &ch: s) {
            h = h * B + ch;
        }
        return h;
    }

    ull get_hash(int l, int r) {
        return p[r] - (l == 0 ? 0 : p[l - 1]) * pows[r - l + 1];
    }

    bool wordBreak(string s, unordered_set<string> &dict) {
        // write your code here
        int n = s.length();
        if (n == 0) return true;

        memset(dp, false, sizeof(dp));
        pows[0] = 1;
        for (int i = 1; i <= n; ++ i) pows[i] = pows[i - 1] * B;
        for (int i = 0; i < n; ++ i) {
            if (i == 0) p[i] = s[i];
            else p[i] = p[i - 1] * B + s[i];
        }

        for (const string &s: dict) {
            dict2.insert(get_hash(s));
            len.insert(s.length());
        }

        return dfs(s);
    }

    bool dfs(const string &s) {
        int n = s.length();
        dp[n] = true;
        int tot = 0;
        for (int i = n - 1; i >= 0; -- i) {
            for (const int &j: len) {
                ull h = get_hash(i, i + j - 1);
                if (dict2.find(h) != end(dict2) && dp[i + j]) {
                    dp[i] = true;
                }
            }
        }

        return dp[0];
    }
private:
    int B = 131;
    ull p[110000], pows[110010];
    bool dp[110010];
    unordered_set<ull> dict2;
    unordered_set<int> len;
};