18

私は最近、回文に変換するために文字列に (任意の場所に) 挿入する必要がある文字の最小数を計算するよう求めるコンテストの問題を見つけました。

たとえば、文字列 "abcbd" が与えられた場合、"a" の後に 1 つ、"d" の後にもう 1 つ、"a d bcbd a " という 2 つの文字を挿入するだけで回文に変換できます。

これは、文字を最後にのみ追加できることを除いて、同じことを要求する同様の問題の一般化のようです-これには、ハッシュテーブルを使用した O(N) での非常に単純な解決策があります。

この問題を解決するためにレーベンシュタイン距離アルゴリズムを変更しようとしましたが、成功していません。これを解決する方法についてのヘルプ（必ずしも効率的である必要はありません。DPソリューションに興味があるだけです）をいただければ幸いです。

4

3 に答える 3

7

注：これは単なる好奇心です。Dav は、DP アルゴリズムに変更して、O(n^2) 時間と O(n^2) 空間で簡単に実行できるアルゴリズムを提案しました (より良い簿記ではおそらく O(n))。

もちろん、この「素朴な」アルゴリズムは、許可された操作を変更する場合に実際に役立つ場合があります。

これは「ナイーブ」なアルゴリズムであり、おそらく巧妙な簿記でより高速にすることができます。

文字列が与えられると、結果の回文の中央を推測し、文字列をその中央付近の回文にするために必要な挿入数を計算しようとします。

文字列の長さが n の場合、2n+1 個の中間 (文字列の直前と直後の 2 つの文字の間の各文字) が存在する可能性があります。

2 つの文字列 L と R (左に 1 つ、右に 1 つ) を与える中央を考えてみます。

挿入を使用している場合、L と R の逆の両方を含む「スーパー」文字列を作成するために、 Longest Common Subsequenceアルゴリズム (DP アルゴリズム) を使用できると思います。Shortest common supersequenceを参照してください。

挿入数が最も少ない中央を選択します。

これは O(n^3) だと思います。（注：それが真実であることを証明しようとはしていません）。

于 2010-02-10T14:56:21.340 に答える
2

私の C# ソリューションは、文字列内で繰り返される文字を探し、それらを使用して挿入数を減らします。programのような単語では、'r' 文字を境界として使用します。'r' の中で、回文にします (再帰的に)。'r' の外側では、左右の文字をミラーリングします。

一部の入力には複数の最短出力があります。出力はtoutptuotまたはoutuputuoです。私の解決策は、可能性の 1 つだけを選択します。

いくつかの実行例:

  • レーダー->レーダー、0 挿入
  • esystem -> metsystem、2 つの挿入
  • メッセージ-> megassagem、3 挿入
  • stackexchange -> stegnahckexekchangets、8回の挿入

まず、入力が既に回文であるかどうかを確認する必要があります。

public static bool IsPalindrome(string str)
{
    for (int left = 0, right = str.Length - 1; left < right; left++, right--)
    {
        if (str[left] != str[right])
            return false;
    }
    return true;
}

次に、入力内の繰り返し文字を見つける必要があります。複数ある場合もあります。メッセージという単語には、最も繰り返される 2 つの文字 (「e」と「s」) があります。

private static bool TryFindMostRepeatedChar(string str, out List<char> chs)
{
    chs = new List<char>();
    int maxCount = 1;

    var dict = new Dictionary<char, int>();
    foreach (var item in str)
    {
        int temp;
        if (dict.TryGetValue(item, out temp))
        {
            dict[item] = temp + 1;
            maxCount = temp + 1;
        }
        else
            dict.Add(item, 1);
    }

    foreach (var item in dict)
    {
        if (item.Value == maxCount)
            chs.Add(item.Key);
    }

    return maxCount > 1;
}

私のアルゴリズムはここにあります：

public static string MakePalindrome(string str)
{
    List<char> repeatedList;
    if (string.IsNullOrWhiteSpace(str) || IsPalindrome(str))
    {
        return str;
    }
    //If an input has repeated characters,
    //  use them to reduce the number of insertions
    else if (TryFindMostRepeatedChar(str, out repeatedList))
    {
        string shortestResult = null;
        foreach (var ch in repeatedList) //"program" -> { 'r' }
        {
            //find boundaries
            int iLeft = str.IndexOf(ch); // "program" -> 1
            int iRight = str.LastIndexOf(ch); // "program" -> 4

            //make a palindrome of the inside chars
            string inside = str.Substring(iLeft + 1, iRight - iLeft - 1); // "program" -> "og"
            string insidePal = MakePalindrome(inside); // "og" -> "ogo"

            string right = str.Substring(iRight + 1); // "program" -> "am"
            string rightRev = Reverse(right); // "program" -> "ma"

            string left = str.Substring(0, iLeft); // "program" -> "p"
            string leftRev = Reverse(left); // "p" -> "p"

            //Shave off extra chars in rightRev and leftRev
            //  When input = "message", this loop converts "meegassageem" to "megassagem",
            //    ("ee" to "e"), as long as the extra 'e' is an inserted char
            while (left.Length > 0 && rightRev.Length > 0 && 
                left[left.Length - 1] == rightRev[0])
            {
                rightRev = rightRev.Substring(1);
                leftRev = leftRev.Substring(1);
            }

            //piece together the result
            string result = left + rightRev + ch + insidePal + ch + right + leftRev;

            //find the shortest result for inputs that have multiple repeated characters
            if (shortestResult == null || result.Length < shortestResult.Length)
                shortestResult = result;
        }

        return shortestResult;
    }
    else
    {
        //For inputs that have no repeated characters, 
        //  just mirror the characters using the last character as the pivot.
        for (int i = str.Length - 2; i >= 0; i--)
        {
            str += str[i];
        }
        return str;
    }
}

逆関数が必要であることに注意してください。

public static string Reverse(string str)
{
    string result = "";
    for (int i = str.Length - 1; i >= 0; i--)
    {
        result += str[i];
    }
    return result;
}
于 2014-04-16T16:30:46.503 に答える
1

文字列の最後に追加するC＃ 再帰ソリューション：

2つの基本ケースがあります。長さが1または2の場合。再帰的な場合：極値が等しい場合は、パリンドロームを極値なしで内側の弦にし、極値ありで返します。極値が等しくない場合は、最初の文字を最後に追加し、パリンドロームを前の最後の文字を含む内側の文字列にします。それを返します。

public static string ConvertToPalindrome(string str) // By only adding characters at the end
    {
        if (str.Length == 1) return str; // base case 1
        if (str.Length == 2 && str[0] == str[1]) return str; // base case 2
        else
        {
            if (str[0] == str[str.Length - 1]) // keep the extremes and call                
                return str[0] + ConvertToPalindrome(str.Substring(1, str.Length - 2)) + str[str.Length - 1];
            else //Add the first character at the end and call
                return str[0] + ConvertToPalindrome(str.Substring(1, str.Length - 1)) + str[0];
        }
    }
于 2012-12-16T03:41:34.150 に答える