2

有人可以帮助我找到可以将给定字符串拆分成的最小回文数的解决方案吗？例子：

abcdef = 6 //the palindromes are (a,b,c,d,e,f)
bbbaxx = 3 //(bbb, a, xx)
level = 1 // (level)
4

2 回答 2

3

将递归与动态规划结合使用

如果字符串是回文，则结果为 1，否则将字符串分成 2 段（每对都必须这样做）并返回每个部分上两次调用 minPalinCount 的最小总和。

在伪代码中你有这样的东西

minPalinCount(s)
    s is a palindrome ?
       return 1
    else
        for each position in s
           s1,s2 = s split in 2 at this position
           count = min(minPalinCount(s1) + minPalinCount(s2), count)
        return count

在 C++ 中

#include <algorithm>
using namespace std;


bool ispalind(string s1)
{
    int s1i = 0;
    while (s1i < s1.size())
    {
        if (s1[s1i] != s1[s1.size() - 1 - s1i ])
            return false;
        s1i++;
    }
    return true;
}

int palindromeCount(string a)
{
    if (ispalind(a))
        return 1;
    else
    {
        int min = a.size();
        for (int i = 1; i < a.size() ; i++)
            min = std::min(palindromeCount(a.substr(0, i)) + palindromeCount(a.substr(i, a.size() - i)), min);
        return min;
    }
}
于 2012-05-19T21:09:10.487 回答
3

在我的脑海中，我可以想到一个动态编程解决方案。M[i,j]--> 表示从 i 开始到 j 结束的回文......如果这样的回文存在，则为真] == true && Str[i]==str[j] 将这些东西存储在一个由结束索引作为键的适当数据结构中，我们可以从以'n'结尾的回文然后在索引处结束的回文向后遍历这个结构其中回文开始于前一个回文以 n 结束，依此类推。

O(n^2)。不确定是否有更好的贪婪分治算法，

于 2012-05-19T18:00:06.027 回答