Минимални вметнувања за да се формира палиндром со дозволени пермутации


Ниво на тешкотија Медиум
Често прашувано во Амазон CodeNation Директи Google Навистина Интуитивно
Динамичко програмирање Стринг

Проблемот „Минимални вметнувања за да се формира палиндром со дозволени пермутации“ наведува дека ви е дадена низа со мали букви. Изјавата за проблемот бара да се открие минималното вметнување на карактерот во низата дека тој може да стане Палиндром. Позицијата на знаците може да се смени во низа.

пример

Минимални вметнувања за да се формира палиндром со дозволени пермутации

malyalam
1

Објаснување

Ако можеме да додадеме „а“ на почетната низа, можеме да создадеме палиндром.

madaam
1

Објаснување

Или додадете 'd' или 'a' за да ја направите оригиналната низа палиндром.

Алгоритам

  1. Поставете ја должината на низата на l и излез на 0.
  2. Прогласи ан број низа.
  3. Чувајте го и одржувајте го броењето на секој карактер во низа.
  4. Поминете ја низата почнувајќи од 0 до додека сум <26.
    1. Проверете дали countChar [i] % 2 == 1,
      1. Ако е точно, тогаш направете излез ++.
  5. Ако излезот е еднаков на 0, тогаш вратете го 0.
  6. Друг повратен излез-1.

Објаснување

Ви се дава А. низа, задачата што ви е дадена е да откриете минимално вметнување што треба да се изврши во низа, така што станува Палиндром. Позицијата на знаците може да се смени во низа. Toе ја изброиме појавата на карактерот на низата и ќе ја зачуваме во низа. Бидејќи идејата што стои позади тоа е дека кога стрингот е палиндром, има само еден знак што може да биде непарен кога должината на низата е непарна. Освен тоа, сите карактери имаат дури и фреквенција. Значи, треба да најдеме карактери што се појавуваат непарен број пати.

Toе ги броиме сите знаци во влезната низа и ќе ги зачуваме во низа. Како што веќе споменавме, низата што е палиндром може да има само еден карактер што се појавува непарен број пати. Значи, излезот ќе биде еден помалку од бројот на карактери. По зачувување на секоја појава на низа во карактер во низа. Потоа правиме низа што поминува од 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

Анализа на сложеност

Временска комплексност

Тој) каде „Н“ е бројот на знаци во влезната низа.

Комплексноста на просторот

О (1), затоа што создадовме дополнителна низа со постојана големина. Така, комплексноста на просторот е постојана.