139. 单词拆分

发表于 分类于 阅读次数： Waline： 本文字数： 341 阅读时长 ≈ 1 分钟

考点

  • 字典树
  • 划分DP

思路

将数组拆分为若干个相邻的连续子数组，那么以最后一个元素的角度解题：

  1. 要么它是某个单词的结尾，对答案有贡献
  2. 要么它没贡献

写出如下DP：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
 public:
  bool wordBreak(string s, vector<string>& wordDict) {
    int mx = 0;
    for (int i = 0; i < wordDict.size(); ++i)
      mx = max(mx, (int)wordDict[i].size());
    unordered_set<string> st(wordDict.begin(), wordDict.end());
    int n = s.size();
    bool f[305];
    memset(f, 0, sizeof(f));
    f[0] = 1;
    for (int i = 1; i <= n; ++i) {
      for (int j = i; j >= max(1, i + 1 - mx); --j) {
        if (f[j - 1] && st.find(s.substr(j - 1, i - j + 1)) != st.end()) {
          f[i] = 1;
          break;
        }
      }
    }
    return f[n];
  }
};

由于substr的复杂度是线性的，也可以用字典树把它优化一下：

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
class Solution {
 public:
  int trie[20005][26], ed[20005], tot = 1;
  void add(string& s) {
    int p = 1;
    for (char& chr : s) {
      int id = chr - 'a';
      if (trie[p][id] == 0) trie[p][id] = ++tot;
      p = trie[p][id];
    }
    ed[p] = 1;
  }
  bool wordBreak(string s, vector<string>& wordDict) {
    int m = 0;
    memset(trie, 0, sizeof(trie)), memset(ed, 0, sizeof(ed));
    for (int i = 0; i < wordDict.size(); ++i) {
      add(wordDict[i]);
      m = max(m, (int)wordDict[i].size());
    }
    int n = s.size();
    bool f[305];
    memset(f, 0, sizeof(f));
    f[0] = 1;
    // 由于字典树是正向保存的，所以DP改为Push方向
    for (int i = 0; i < n; ++i) {
      if (!f[i]) continue;
      int p = 1;
      for (int j = i; j < n && j - i + 1 <= m; ++j) {
        if (!trie[p][s[j] - 'a']) break;
        p = trie[p][s[j] - 'a'];
        if (ed[p]) f[j + 1] = 1;
      }
    }
    return f[n];
  }
};