题目描述

题目链接

给你一个字符串 s 和一个字符串列表 wordDict 作为字典。请你判断是否可以利用字典中出现的单词拼接出 s 。

注意：不要求字典中出现的单词全部都使用，并且字典中的单词可以重复使用。

 

示例 1：

1
2
3
输入: s = "leetcode", wordDict = ["leet", "code"]
输出: true
解释: 返回 true 因为 "leetcode" 可以由 "leet" 和 "code" 拼接成。

示例 2：

1
2
3
4
输入: s = "applepenapple", wordDict = ["apple", "pen"]
输出: true
解释: 返回 true 因为 "applepenapple" 可以由 "apple" "pen" "apple" 拼接成。
     注意，你可以重复使用字典中的单词。

示例 3：

1
2
输入: s = "catsandog", wordDict = ["cats", "dog", "sand", "and", "cat"]
输出: false

算法1

(DP) $O(n^3)$

分析：
题目意思是需要使用给定的字典中的单词拼接出目标字符串，可以将题目抽象为： 将一个字符串分割成为若干部分，使得每一部分都能够在字典中找到

因此，首先需要使用一个哈希表来存储所有的字典中的单词，方便后续查找划分出的部分是否在字典中

其次，我们可以发现，每种划分方法代表的是一种状态下的方案，而不是单单某一种方案，因此需要可以考虑使用 DP 来计算当前划分方案是否合法

DP

  • 集合：定义 f[i]为从 1 ~ i是否是一种合理的划分方案
  • 属性：bool，判断当前的划分方案是否合法
  • 转移: 针对当前的起点 i， 终点 j，如果 s[i ~ j] 存在于字典中，那么，当前划分方案是否合法取决于 1 ~ i - 1是否合法，而根据定义， 1 ~ i - 1的合法性刚好就是 f[i - 1]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
class Solution {
public:

    bool wordBreak(string s, vector<string>& wordDict) {
        int n = s.size();
        
        unordered_set<string> hash;
        for(auto word : wordDict) hash.insert(word);

        vector<bool> f(n + 1);
        f[n] = true;

        for(int i = n - 1; i >= 0; i --)
            for(int j = i; j < n; j ++)
            {
                if( hash.count(s.substr(i, j - i + 1)) && f[j + 1])
                {
                    f[i] = true;
                    break;
                }
            }

        return f[0];
    }
};

注：

  • 关于此处代码中的 f[i]，是为了计算方便，从后往前搜索的，与正常的思维逆反过来即可
  • 按照相反的定义 f[n] 表示从 n ~ n的方案合法性
  • 那么f[i] 的合法性同理的，由 s[i, j] 和 f[j + 1]共同决定

算法2

(DP + 字符串哈希) $O(n^2)$

由于朴素的 DP 算法中，每次需要调用 substr来取得某一段的字符串值，但是这样的话复杂度与那一段的长度相关，因此会造成复杂度上升，因此，需要考虑一种方法将这个过程的复杂度降低

可以考虑字符串哈希的方法，将字典中的所有字符串映射成为 P 进制的数，同时，在将字符串进行划分时，也映射成为相应进制的数字，这样可以在 $O(1)$ 的时间内判断字符串是否在字典之中，成功优化时间复杂度

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
class Solution {
public:
    typedef unsigned long long ULL;
    unordered_set<ULL> hash;

    bool wordBreak(string s, vector<string>& wordDict) {
        int n = s.size();

        int P = 131;

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

        vector<bool> f(n + 1);
        f[n] = true;

        for(int i = n - 1; i >= 0; i --)
        {
            ULL h = 0;
            for(int j = i; j < n; j ++)
            {
                h = h * P + s[j];
                if( hash.count(h) && f[j + 1])
                {
                    f[i] = true;
                    break;
                }       
            }
        }

        return f[0];
    }
};