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

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

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

根据美光的要求进行编辑: 这是计算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);
     }
   } 
 }
} 

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];
}

一个等价的问题是计算字符串的Snip数。

假设你想用最少的剪刀剪一根绳子,这样剩下的每一块都是回文。我们称之为线的剪数。也就是说,snip数总是等于给定字符串中最小回文数的1。长度n的每个字符串最多有snip个数n-1,每个回文有snip个数0。这里是工作的python代码。

def snip_number(str):
    n=len(str)
 
 #initialize Opt Table
 # Opt[i,j] = min number of snips in the substring str[i...j]
 
    Opt=[[0 for i in range(n)] for j in range(n) ]
 
 #Opt of single char is 0
    for i in range(n):
     Opt[i][i] = 0
 
 #Opt for adjacent chars is 1 if different, 0 otherwise
    for i in range(n-1):
     Opt[i][i+1]= 1 if str[i]!=str[i+1] else 0
 
 
# we now define sil as (s)substring (i)interval (l) length of the
# interval [i,j] --- sil=(j-i +1) and j = i+sil-1
 
# we compute Opt table entry for each sil length and
# starting index i
 
    for sil in range(3, n+1):
     for i in range(n-sil+1):
       j = i+sil-1
       if (str[i] == str[j] and Opt[i+1][j-1]==0):
         Opt[i][j] = 0
       else:
         snip= min( [(Opt[i][t]+ Opt[t+1][j] + 1 ) for t in range(i,j-1)])
         Opt[i][j] = snip

    return Opt[0][len(str)-1]
#end function snip_number()
mystr=[""for i in range(4)]         
mystr[0]="abc"
mystr[1]="ohiho"
mystr[2]="cabacdbabdc"
mystr[3]="amanaplanacanalpanama aibohphobia "


for i in range(4):
     print mystr[i], "has snip number:", snip_number(mystr[i])
     
# abc has snip number: 2
# ohiho has snip number: 0
# cabacdbabdc has snip number: 2
# amanaplanacanalpanama aibohphobia  has snip number: 1

bool ispalindrome(string inp)
{
    if(inp == "" || inp.length() == 1)
    {
        return true;
    }
    string rev = inp;

    reverse(rev.begin(), rev.end());

    return (rev == inp);
}

int minsplit_count(string inp)
{
    if(ispalindrome(inp))
    {
        return 0;
    }

    int count= inp.length();

    for(int i = 1; i < inp.length(); i++)
    {
        count = min(count, 
                      minsplit_count(inp.substr(0, i))              + 
                      minsplit_count(inp.substr(i, inp.size() - i)) + 
                      1);
    }

    return count;
}

O(n^3)解决方案。递归迭代字符串。为每一个字母建立每一个回文与这封信作为回文的开始。注意奇数和偶数回文。重复直到字符串结束。如果在字符串的末尾回文数是最小的,那么记住你是如何得到的。如果字符串中当前回文计数和剩余字母的总和大于当前回文计数最小值,则不要进一步迭代。

一个优化:当发现回文从字符串的末尾开始并搜索当前字母的出现位置时。将子字符串测试为“回文”。不要从最短的回文开始,这不是最优的。