1745. 分割回文串 IV

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

考点

  • 划分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
24
25
26
27
28
29
30
31
32
class Solution {
 public:
  bool checkPartitioning(string s) {
    // manacher打表, 第i个字符为中心时的最长回文半径
    string t = "";
    for (char& chr : s) t.push_back('#'), t.push_back(chr);
    t.push_back('#');
    int p[4005], r = 0, c = 0;
    for (int i = 1; i <= t.size(); ++i) {
      p[i] = 1;
      int mirror = 2 * c - i;
      if (i <= r && mirror >= 1) p[i] = min(r - i + 1, p[mirror]);
      while (i - p[i] >= 1 && i + p[i] <= t.size() &&
             t[i - p[i] - 1] == t[i + p[i] - 1])
        p[i]++;
      if (i + p[i] - 1 > r) c = i, r = i + p[i] - 1;
    }
    // DP
    bool f[2005][2005];
    memset(f, 0, sizeof(f));
    f[0][0]=1;
    for (int j = 1; j <= 3; ++j) {
      for (int r = 1; r <= s.size(); ++r) {
        for (int l = r; l >= j; --l) {
          if (f[j][r]) break;
          f[j][r] |= f[j - 1][l - 1] & (p[l + r] >= r - l + 1);
        }
      }
    }
    return f[3][s.size()];
  }
};

当然，也可以滚动数组压缩掉第一维

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
class Solution {
 public:
  bool checkPartitioning(string s) {
    // manacher打表, 第i个字符为中心时的最长回文半径
    string t = "";
    for (char& chr : s) t.push_back('#'), t.push_back(chr);
    t.push_back('#');
    int p[4005], r = 0, c = 0;
    for (int i = 1; i <= t.size(); ++i) {
      p[i] = 1;
      int mirror = 2 * c - i;
      if (i <= r && mirror >= 1) p[i] = min(r - i + 1, p[mirror]);
      while (i - p[i] >= 1 && i + p[i] <= t.size() &&
             t[i - p[i] - 1] == t[i + p[i] - 1])
        p[i]++;
      if (i + p[i] - 1 > r) c = i, r = i + p[i] - 1;
    }
    // DP
    bool f[2005];
    memset(f, 0, sizeof(f));
    f[0] = 1;
    for (int j = 1; j <= 3; ++j) {
      for (int r = s.size(); r >= 1; --r) {
        f[r] = 0;
        for (int l = r; l >= j; --l) {
          if (f[r]) break;
          f[r] |= f[l - 1] & (p[l + r] >= r - l + 1);
        }
      }
    }
    return f[s.size()];
  }
};