10

特定の文字列を回文に変換するために必要な挿入の最小数を見つけるために、文字列（lcs_string）の最長共通部分列とその逆を見つけます。したがって、行われる挿入の数はlength（s）-length（lcs_string）です。

挿入の数を知る上で同等の回文文字列を見つけるには、どのような方法を採用する必要がありますか？

例えば ​​：

1）azbzczdzez

必要な挿入数：5回文文字列：azbzcezdzeczbza

同じ文字列に対して複数の回文文字列が存在する場合がありますが、1つの回文文字列のみを検索したいですか？

4

5 に答える 5

13

インデックスで始まりインデックスで終わるS[i, j]文字列のサブ文字列（両方を含む）を表し、の最適なソリューションになります。Sijc[i, j]S[i, j]

明らかに、c[i, j] = 0 if i >= j。

一般的に、再発があります：

ここに画像の説明を入力してください

于 2012-05-24T07:18:54.503 に答える
1

VenomFangsの答えを詳しく説明するために、これに対する単純な動的プログラミングソリューションがあります。ここで許可されている操作は文字の挿入（削除、更新なし）のみであると想定していることに注意してください。Sをn文字の文字列とします。このための単純な再帰関数Pは次のとおりです。

    = P [i+1 .. j-1], if S[i] = S[j]

P [i..j]

    = min (P[i..j-1], P[i+1..j]) + 1,

これが真実である理由についてさらに説明が必要な場合は、コメントを投稿してください。少し考えればわかりやすいですが、喜んで説明します。ちなみに、これは使用するLCS関数の正反対であるため、ソリューションが実際に最適であることを検証します。もちろん、それは完全に可能です、もしそうなら、誰かが私に知らせてくれます！

編集：回文自体を説明するために、これは次のように簡単に行うことができます： 上記のように、P [1..n]は、この文字列を回文にするために必要な挿入数を示します。上記の2次元配列が作成されたら、次のように回文を見つけます。

i = 1、j=nから始めます。ここで、string output = "";

while(i < j)
{
    if (P[i][j] == P[i+1][j-1]) //this happens if no insertions were made at this point
    {
        output = output + S[i];
        i++;
        j--;
    }
    else
    if (P[i][j] == P[i+1][j]) //
    {
        output = output + S[i];
        i++;
    }
    else
    {
        output = S[j] + output;
        j--;
    }
 }
 cout<<output<<reverse(output);
 //You may have to be careful about odd sized palindromes here,
 // I haven't accounted for that, it just needs one simple check

それはより良い読書になりますか？

于 2012-05-24T03:37:54.063 に答える
0

このソリューションは、動的計画法ソリューションのように見えます。

次の投稿で答えを見つけることができるかもしれません：文字列を回文に変えるのに必要な文字数を計算するにはどうすればよいですか？

于 2012-05-24T00:57:08.443 に答える
-1

O（n）のPHPソリューション

function insertNode(&$arr, $idx, $val) {
    $arr = array_merge(array_slice($arr, 0, $idx), array($val), array_slice($arr, $idx));
}
function createPalindrome($arr, $s, $e) {
    $i = 0;
    while(true) {
        if($s >= $e) {
            break;
        } else if($arr[$s] == $arr[$e]) {
            $s++; $e--; // shrink the queue from both sides 
            continue;
        } else {
            insertNode($arr, $s, $arr[$e]);
            $s++;
        }
    }
    echo implode("", $arr);
}
$arr = array('b', 'e', 'a', 'a', 'c', 'd', 'a', 'r', 'e');
echo createPalindrome ( $arr, 0, count ( $arr ) - 1 );
于 2016-10-18T09:10:09.147 に答える
-2

単純。下記参照 ：）

        String pattern = "abcdefghgf";
        boolean isPalindrome = false;
        int i=0,j=pattern.length()-1;
        int mismatchCounter = 0;

        while(i<=j)
        {
            //reverse matching
            if(pattern.charAt(i)== pattern.charAt(j))
                {
                    i++; j--; 
                    isPalindrome = true;
                    continue;
                }

            else if(pattern.charAt(i)!= pattern.charAt(j))
                {
                    i++;
                    mismatchCounter++;
                }


        }
        System.out.println("The pattern string is :"+pattern);
        System.out.println("Minimum number of characters required to make this string a palidnrome : "+mismatchCounter);
于 2016-06-16T15:54:53.550 に答える