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の2つの呼び出しの最小合計を返します。

擬似コードでは、次のようなものがあります

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、そうでない場合はM [i、j] = true iff M [i + 1、j-1 ] == true && Str [i] == str [j]このようなものを終了インデックスでキー設定された適切なデータ構造に格納すると、この構造を「n」で終わる回文から逆方向にトラバースでき、その後にインデックスで終わる回文が続きますnで終わる前の回文に対して回文が開始された場所など。

O（n ^ 2）。より良い分割統治法があるかどうかわからない、

于 2012-05-19T18:00:06.027 に答える