كيف يمكنني حساب عدد الأحرف المطلوبة لتحويل سلسلة إلى palindrome؟

Question

لقد وجدت مؤخرا مشكلة مسابقة تطلب منك حساب الحد الأدنى لعدد الأحرف التي يجب إدراجها (في أي مكان) في سلسلة لتحويلها إلى palindrome.

على سبيل المثال، نظرا للسلسلة: "ABCBD" يمكننا تشغيله إلى palindrome عن طريق إدخال حرفين فقط: واحد بعد "A" وآخر بعد "D": "دBCBD.أ".

يبدو أن هذا تعميم لمشكلة مماثلة يسأل عن نفس الشيء، باستثناء الأحرف لا يمكن إضافته إلا في النهاية - وهذا يحتوي على حل بسيط جدا في O (N) باستخدام جداول التجزئة.

لقد كنت أحاول تعديل levenshtein خوارزمية المسافة لحل هذه المشكلة، ولكن لم تكن ناجحة. أي مساعدة حول كيفية حل هذا (لا يجب أن تكون بالضرورة أن تكون فعالة، أنا مهتم فقط في أي حل DP) موضع تقدير.

Answer 1

ملاحظة: هذا مجرد فضول. اقترح DAV خوارزمية يمكن تعديلها إلى خوارزمية موانئ دبي للتشغيل في O (N ^ 2) وقتا ومساحة O (N ^ 2) بسهولة (وربما O (n) مع تحسين الدفاتر).

بالطبع، قد تأتي خوارزمية "ساذجة" في الواقع إذا قررت تغيير العمليات المسموح بها.

---

فيما يلي خوارزمية ساذجة، والتي يمكن أن تصنع بشكل أسرع مع مسك الدفاتر الذكية.

بالنظر إلى سلسلة، نعتقد منتصف palindrome الناتج ثم حاول حساب عدد إدراج مطلوبة لجعل السلسلة palindrome حول هذا المنتصف.

إذا كانت السلسلة طول N، فهناك Middles 2n + 1 محتمل (كل حرف، بين حرفين، فقط قبل وبعد السلسلة).

لنفترض أننا نعتبر منتصفا يعطينا سلنتين l و r (واحد إلى اليسار وواحد إلى اليمين).

إذا كنا نستخدم إدراج، فأنا أصدق أطول ظهورية لاحق يمكن الآن استخدام الخوارزمية (التي هي خوارزمية DP) الآن سلسلة إنشاء "Super" تحتوي على كل من L وعكس R، انظر أقصر مروع مشترك.

اختر الوسط الذي يمنحك أصغر عدد إدراجات.

هذا هو O (ن ^ 3). (ملاحظة: لم أحاول إثبات أنه صحيح).

Answer 2

يحث حل C # الخاص بي أحرف متكررة في سلسلة ويستخدمها لتقليل عدد الإدراج. في كلمة مثل برنامج, ، أستخدم الشخصيات "r" كحد أقصى. داخل "ص"، أجعل هذا palindrome (متكرر). خارج "ص"، أقابل الشخصيات على اليسار واليمين.

بعض المدخلات لديها أكثر من أقصر الإنتاج: انتاج يمكن ان يكون toutptuot. أو Outuputuo.. وبعد يحدد الحل الخاص بي واحد فقط من الاحتمالات.

يعمل بعض الأمثلة على:

• رادار -> رادار, ، 0 الإدراج
• esystem -> نظام metsystem., ، 2 الإدراج
• رسالة -> megassagem., ، 3 الإدراج
• stackexchange. -> stegnahckexekchangets., ، 8 الإدراج

أولا أحتاج إلى التحقق مما إذا كانت الإدخال بالفعل palindrome:

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

ثم أحتاج إلى العثور على أي أحرف متكررة في الإدخال. قد يكون هناك أكثر من واحد. الكلمة رسالة لديه شخصين أكثر تكرارا ('E' و '):

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

Answer 3

ج # حل العودية مضيفا إلى نهاية السلسلة:

هناك 2 حالات قاعدة. عندما يكون الطول 1 أو 2. القضية العودية: إذا كانت التطرف متساويا، فقم بإنشاء السلسلة الداخلية دون النقيضين وإرجاع ذلك مع التطرف. إذا كانت التطرف غير متساوية، فقم بإضافة الحرف الأول إلى النهاية وجعل palindrome السلسلة الداخلية بما في ذلك الحرف الأخير السابق. عودة ذلك.

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