Палиндромды қалыптастыру үшін минималды кірістірулерге рұқсат етіледі


Күрделілік дәрежесі орта
Жиі кіреді Amazon CodeNation Directi Google шынында Intuit
Динамикалық бағдарламалау String

«Пермутациямен палиндромды қалыптастыруға арналған минималды қосымшалар» проблемасында сізге барлық әріптермен кіші әріптермен Жол берілгендігі айтылған. Есептер Палиндромға айналуы мүмкін жолға таңбаның минималды кірістіруін білуді сұрайды. Символдардың орнын жолда өзгертуге болады.

мысал

Палиндромды қалыптастыру үшін минималды кірістірулерге рұқсат етіледі

malyalam
1

Түсіндіру

Егер біз бастапқы жолға 'а' қоса алсақ, палиндром жасай аламыз.

madaam
1

Түсіндіру

Бастапқы жол палиндромын жасау үшін 'd' немесе 'a' қосыңыз.

Алгоритм

  1. Жолдың ұзындығын келесіге қойыңыз l және 0-ге дейін шығарыңыз.
  2. Декларациялау бүтін сан массив.
  3. Әр таңбаның санын жолда сақтаңыз және сақтаңыз.
  4. Массивті 0-ден i <26-ға дейін өтіңіз.
    1. Тексеріңіз countChar [i] % 2 == 1,
      1. Егер рас болса, онда ++ мәнін шығарыңыз.
  5. Егер шығыс 0-ге тең болса, онда 0 мәнін қайтарыңыз.
  6. Басқа қайтару нәтижесі-1.

Түсіндіру

Сізге а жол, сіздің тапсырмаңыз Палиндромға айналатындай етіп жолға енгізілетін минималды кірістіруді табу болып табылады. Символдардың орнын жолда өзгертуге болады. Біз жолдың таңбасының пайда болуын санап, оны массивке сақтаймыз. Мұндағы идея: жол палиндром болған кезде, жол ұзындығы тақ болған кезде тақ болатын жалғыз ғана таңба болады. Одан басқа, барлық таңбалардың біркелкі жиілігі бар. Сондықтан тақ сан рет кездесетін таңбаларды табуымыз керек.

Біз енгізу жолындағы әрбір таңбаны санап, оны массивке сақтаймыз. Жоғарыда айтқанымыздай, палиндромды жол тек бірнеше рет болатын бір таңбадан тұрады. Демек, шығу таңбалар санынан бір кем болады. Әрбір символдар тізбегін жиымға сақтағаннан кейін. Содан кейін біз i = 0-ден i-ге дейінгі массивті 26-дан кем жасаймыз. Себебі барлығы 26 таңба бар және берілген жолда 26 таңбаның пайда болу ықтималдығы болады деп ойлауымыз керек.

Массивті айналып өтіп, әр санақты 2-ге бөлгенде, егер ол рас болса, 1-де қалдық қалады ма, сонда ол шығыс санын 1-ге көбейтеді (нәтиже ++). Массивті айналып өткеннен кейін, егер санау нөлге тең болса, онда біз таңбада тақ ештеңе таппаймыз дегенді білдіреді, егер жол палиндромды болса, біз 0-ге ораламыз, біз қайтарамыз (шығыс-1), өйткені біз қазірдің өзінде шығарудың біреуі аз болатынын айтқанбыз таңбалар саны, демек, біз нәтиже алдық.

код

Табуға арналған C ++ коды, пермутацияға рұқсат етілген палиндром қалыптастыру үшін минималды қосымшалар

#include<iostream>

using namespace std;

int getMinimumInsertion(string str)
{
    int l = str.length(),output = 0;

    int countChar[26] = { 0 };
    for (int i = 0; i < l; i++)
        countChar[str[i] - 'a']++;

    for (int i = 0; i < 26; i++)
        if (countChar[i] % 2 == 1)
            output++;

    return (output == 0) ? 0 : output - 1;
}
int main()
{
    string str = "malyalam";
    cout << getMinimumInsertion(str);

    return 0;
}
1

Java кодын табуға рұқсат етілген пиндромды қалыптастыруға арналған минималды қосымшалар

class insertionToPalindrome
{
    public static int getMinimumInsertion(String str)
    {
        int l = str.length(),output = 0;

        int countChar[] = new int[26];

        for (int i = 0; i < l; i++)
            countChar[str.charAt(i) - 'a']++;

        for (int i = 0; i < 26; i++)
        {
            if (countChar[i] % 2 == 1)
                output++;
        }

        return (output == 0) ? 0 : output - 1;
    }
    public static void main(String[] args)
    {
        String str = "malyalam";
        System.out.println(getMinimumInsertion(str));
    }
}
1

Күрделілікті талдау

Уақыттың күрделілігі

O (N) қайда «N» - бұл енгізу жолындағы символдар саны.

Ғарыштың күрделілігі

O (1), өйткені біз тұрақты өлшемі бар қосымша массив құрдық. Осылайша кеңістіктің күрделілігі тұрақты болады.