如何将字符串分成尽可能少的回文？

Question

这是一个采访问题:"你给了一个字符串,你想把它分成尽可能少的字符串,这样每个字符串都是一个回文".(我猜一个字符串被认为是回文,即"abc"分为"a","b","c".)

你会怎么回答？

Answer 1

首先找到字符串中的所有回文，使得 L[i][j] 表示以 S[i] 结尾的第 j 个最长回文的长度。假设 S 是输入字符串。这可以在 O(N^2) 时间内完成，首先考虑长度为 1 的回文，然后再考虑长度为 2 的回文，依此类推。在您知道所有长度 i-2 回文后，找到长度 i 回文是单个字符比较的问题。

之后这是一个动态规划问题。让 A[i] 表示 Substring(S,0,i-1) 可以分解成的最小回文数。

A[i+1] = min_{0 <= j < length(L[i])} A[i - L[i][j]] + 1;

根据 Micron 的要求进行编辑： 这是对 L[i][j] 进行计算背后的想法。我写这个只是为了传达这个想法，代码可能有问题。

// Every single char is palindrome so L[i][0] = 1;
vector<vector<int> > L(S.length(), vector<int>(1,1));

for (i = 0; i < S.length(); i++) {
 for (j = 2; j < S.length; j++) {
   if (i - j + 1 >= 0 && S[i] == S[i-j + 1]) {
     // See if there was a palindrome of length j - 2 ending at S[i-1]
     bool inner_palindrome = false;
     if (j ==2) {
      inner_palindrome = true;
     } else {
       int k = L[i-1].length;
       if (L[i-1][k-1] == j-2 || (k >= 2 && L[i-1][k-2] == j-2)) {
         inner_palindrome = true;
       }
     }
     if (inner_palindrome) {
       L[i].push_back(j);
     }
   } 
 }
} 

Answer 2

您可以使用 Rabin-Karp 指纹识别来预处理字符串，在 O(n^2) 时间内完成此操作，以在 O(n^2) 时间内找到所有回文。预处理后，您运行类似于以下的代码：

np(string s) {
  int a[s.size() + 1];
  a[s.size()] = 0;
  for (int i = s.size() - 1; i >= 0; i--) {
    a[i] = s.size() - i;
    for (int j = i + 1; j <= s.size(); j++) {
      if (is_palindrome(substr(s, i, j))) // test costs O(1) after preprocessing
        a[i] = min(a[i], 1 + a[j]);
  }
  return a[0];
}