문자열을 팔린 드롬으로 바꾸는 데 필요한 문자 수를 어떻게 계산할 수 있습니까?

StackOverflow https://stackoverflow.com/questions/2237021

문제

최근에 문자열에 (어디서나) 삽입 해야하는 최소 수의 문자를 계산하여 팔린 드롬으로 바꾸는 컨테스트 문제를 발견했습니다.

예를 들어, 문자열이 주어지면 : "ABCBD"는 "A"이후 하나와 "D"후에는 두 문자를 삽입하여 Palindrome으로 바꿀 수 있습니다.디BCBDㅏ".

이것은 문자를 마지막에만 추가 할 수있는 경우를 제외하고는 동일한 문제를 요구하는 유사한 문제의 일반화 인 것 같습니다. 해시 테이블을 사용하는 O (n)의 매우 간단한 솔루션이 있습니다.

나는 수정하려고 노력했다 Levenshtein 거리 알고리즘 이 문제를 해결하기 위해서는 성공하지 못했습니다. 이를 해결하는 방법에 대한 도움 (반드시 효율적 일 필요는 없지만 DP 솔루션에 관심이 있음)에 감사 할 것입니다.

도움이 되었습니까?

해결책

참고 : 이것은 단지 호기심 일뿐입니다. DAV는 DP 알고리즘으로 수정하여 O (n^2) 시간 및 O (N^2) 공간에서 쉽게 실행되도록 (및 더 나은 부기)로 실행할 수있는 알고리즘을 제안했습니다.

물론,이 '순진한'알고리즘은 허용 작업을 변경하기로 결정한 경우 실제로 유용 할 수 있습니다.

다음은 '순진한'알고리즘이 있습니다. 아마도 영리한 부기로 더 빨리 만들 수 있습니다.

문자열이 주어지면, 우리는 결과적인 palindrome의 중간을 추측 한 다음 문자열을 그 중간에 팔린 드롬으로 만드는 데 필요한 삽입물 수를 계산하려고 시도합니다.

문자열이 길이 n 인 경우, 2n+1 가능한 중간 (각 문자, 문자열 직전과 직후)이 있습니다.

우리가 우리에게 두 개의 문자열을주는 중간을 고려한다고 가정 해 봅시다.

인서트를 사용하는 경우 믿습니다 가장 긴 일반적인 후속 알고리즘 (DP 알고리즘)을 사용할 수 있습니다. 가장 짧은 공통 초대장.

가장 작은 숫자 인서트를 제공하는 중간을 선택하십시오.

이것은 내가 믿는 O (n^3)입니다. (참고 : 나는 그것이 사실임을 증명하려고 시도하지 않았습니다).

다른 팁

내 C# 솔루션은 문자열의 반복 문자를 찾고 삽입 수를 줄이기 위해 사용합니다. 같은 단어로 프로그램, 나는 'r'문자를 경계로 사용합니다. 'R's 안에서, 나는 그것을 팔린 드롬 (재귀 적으로)으로 만듭니다. 'R'외에는 왼쪽과 오른쪽의 캐릭터를 반영합니다.

일부 입력에는 출력이 가장 짧습니다. 산출 할 수 있습니다 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'및 '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;
}

씨# 문자열 끝에 추가되는 재귀 솔루션 :

기본 사례가 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];
        }
    }
라이센스 : CC-BY-SA ~와 함께 속성
제휴하지 않습니다 StackOverflow
scroll top