2707. 字符串中的额外字符

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

考点

  • 划分DP
  • 字典树

思路

将数组划分为若干个连续的子数组，那么以当前字符为结尾，只有两种可能

要么它处在一个是单词的情况，没有开销

要么它处在一个非法单词的情况，有开销，开销等于非法单词的长度，从而写出下面的DP：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
 public:
  int minExtraChar(string s, vector<string>& dictionary) {
    s = "0" + s;
    int n = s.size()-1;
    // 考虑下标1~i，用字典组成的字符串且剩的最小
    int f[55];
    memset(f, 0x3f, sizeof(f));
    f[0] = 0;
    unordered_set<string> st(dictionary.begin(), dictionary.end());
    for (int i = 1; i <= n; ++i) {
      for (int j = i; j >= 1; --j) {
        int len = i - j + 1;
        if (st.find(s.substr(j, len)) == st.end())
          // 作为剩的
          f[i] = min(f[i], f[j - 1] + len);
        else
          f[i] = min(f[i], f[j - 1]);
      }
    }
    return f[n];
  }
};

正如刚才所说，s[i]要么组成合法单词，要么和1 ~ i - 1中的剩余字符组在一起，

不妨先假设s[i]就是垃圾字符，后续再用合法单词更新最小值即可

所以上面的这行代码

1
f[i] = min(f[i], f[j - 1] + len);

可以改成下面这个

1
f[i] = f[i - 1] + 1;

可以省一丁点常数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
public:
    int minExtraChar(string s, vector<string>& dictionary) {
        s = "0" + s;
        int n = s.size() - 1;
        // 考虑下标1~i，用字典组成的字符串且剩的最小
        int f[55];
        memset(f, 0x3f, sizeof(f));
        f[0] = 0;
        unordered_set<string> st(dictionary.begin(), dictionary.end());
        for (int i = 1; i <= n; ++i) {
            f[i] = f[i - 1] + 1;
            for (int j = i; j >= 1; --j) {
                int len = i - j + 1;
                if (st.find(s.substr(j, len)) != st.end())
                    f[i] = min(f[i], f[j - 1]);
            }
        }
        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
37
38
class Solution {
 public:
  int trie[2505][26], ed[2505], tot = 1;
  void add(string& s) {
    int p = 1;
    for (auto& chr : s) {
      int idx = chr - 'a';
      if (trie[p][idx] == 0) trie[p][idx] = ++tot;
      p = trie[p][idx];
    }
    ed[p] = 1;
  }
  int minExtraChar(string s, vector<string>& dictionary) {
    s = "0" + s;
    int n = s.size() - 1;
    // 字典树初始化
    int m = 0;
    memset(trie, 0, sizeof(trie)), memset(ed, 0, sizeof(ed));
    for (int i = 0; i < dictionary.size(); ++i) {
      m = max(m, (int)dictionary[i].size());
      reverse(dictionary[i].begin(), dictionary[i].end());
      add(dictionary[i]);
    }
    // 考虑下标1~i，用字典组成的字符串且剩的最小
    int f[55];
    memset(f, 0x3f, sizeof(f));
    f[0] = 0;
    for (int i = 1; i <= n; ++i) {
      f[i] = f[i - 1] + 1;
      int p = 1;
      for (int j = i; j >= max(1,i + 1 - m) && trie[p][s[j] - 'a']; --j) {
        p = trie[p][s[j] - 'a'];
        if (ed[p]) f[i] = min(f[i], f[j - 1]);
      }
    }
    return f[n];
  }
};