2472. 不重叠回文子字符串的最大数目

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

考点

  • 划分DP
  • 贪心
  • 回文串
  • manacher

思路

题目表达的含义是，每个回文串只能用一次，比如abba

如果你把bb看作回文串，那么abba就必须拆成a[bb]a，所以是划分DP的裸题，容易得到下面的AC代码：

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
class Solution {
 public:
  int maxPalindromes(string s, int k) {
    int n = s.size();
    s = "0" + s;
    // 打表，所有的回文串
    bool isPalindrome[2005][2005];
    memset(isPalindrome, 0, sizeof(isPalindrome));
    for (int i = n; i >= 1; --i) {
      for (int j = i; j <= n; ++j) {
        if (s[i] == s[j] && (j - i <= 1 || isPalindrome[i + 1][j - 1]))
          isPalindrome[i][j] = 1;
      }
    }
    // DP
    int f[2005];
    memset(f, 0, sizeof(f));
    for (int r = 1; r <= n; ++r) {
      f[r] = f[r - 1];
      if (r + 1 - k <= 0) continue;
      for (int l = r + 1 - k; l >= 1; --l) {
        if (isPalindrome[l][r]) f[r] = max(f[r], f[l - 1] + 1);
      }
    }
    return f[n];
  }
};

我们是每次枚举最后一个区间的回文串可行性

但发现一个事实：不管该区间的回文串的长度与否，最终也仅仅是加一

假设当前有长度大于等于k+2的，那么k或者k+1肯定也是回文

那么可以采取贪心策略，不妨只考虑长度为K和K+1的回文串即可，

其余空间留给前面尽可能地取回文串，这样不一定更优，但是不会更差

下面的AC代码换成了manacher打表回文串，更快：

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
class Solution {
 public:
  int maxPalindromes(string s, int k) {
    // Manacher初始化
    string t = "";
    for (char& chr : s) t.push_back('#'), t.push_back(chr);
    t.push_back('#');
    int n = t.size();
    t = "0" + t;
    // Manacher
    int p[4005], c = 0, r = 0;
    for (int i = 1; i <= n; ++i) {
      int mirror = 2 * c - i;
      p[i] = (i <= r && mirror >= 1) ? min(p[mirror], r - i + 1) : 1;
      while (i - p[i] >= 1 && i + p[i] <= n && t[i - p[i]] == t[i + p[i]])
        p[i]++;
      if (i + p[i] - 1 > r) c = i, r = i + p[i] - 1;
    }
    // DP
    int f[2005];
    memset(f, 0, sizeof(f));
    n = s.size();
    s = "0" + s;
    for (int i = 1; i <= n; ++i) {
      f[i] = f[i - 1];
      // 长度为k的回文串是否存在
      if (i >= k) {
        int l = i + 1 - k, r = i;
        if (p[l + r] >= r - l + 1) f[i] = max(f[i], f[l - 1] + 1);
      }
      // 长度为k+1的回文串是否存在
      if (i >= k + 1) {
        int l = i - k, r = i;
        if (p[l + r] >= r - l + 1) f[i] = max(f[i], f[l - 1] + 1);
      }
    }
    return f[n];
  }
};