Минимални вмъквания за образуване на палиндром с разрешени пермутации  


Ниво на трудност M
Често задавани в Амазонка CodeNation Директи Google Наистина Intuit
Динамично програмиране Низ

Проблемът „Минимални вмъквания за формиране на палиндром с разрешени пермутации“ гласи, че ви се дава низ с всички букви в малки букви. Изявлението за проблем иска да открие минималното вмъкване на символ в низ, който може да стане Palindrome. Позицията на символите може да се променя в низ.

Пример  

Минимални вмъквания за образуване на палиндром с разрешени пермутациищифт

malyalam
1

Обяснение

Ако можем да добавим 'a' към началния низ, можем да създадем палиндром.

madaam
1

Обяснение

Или добавете „d“ или „a“, за да направите оригиналния низ палиндром.

алгоритъм  

  1. Задайте дължината на низа на l и изход на 0.
  2. Декларирайте цяло число масив.
  3. Съхранявайте и поддържайте броя на всеки знак в низ.
  4. Преминете масива, започвайки от 0 до докато i <26.
    1. Проверете дали countChar [i] % 2 == 1,
      1. Ако е вярно, тогава направете изход ++.
  5. Ако изходът е равен на 0, върнете 0.
  6. В противен случай изход-1.

Обяснение

Дадено ви е низ, вашата задача е да откриете минималното вмъкване, което трябва да се направи в низ, така че да стане палиндром. Позицията на символите може да се променя в низ. Ще преброим появата на символа на низ и ще го съхраним в масив. Тъй като идеята зад нея е, че когато низ е палиндром, има само един знак, който може да бъде нечетен, когато дължината на низа е нечетна. Освен това всички знаци имат дори честота. Затова трябва да намерим знаци, които се появяват нечетен брой пъти.

Вижте също
Каменна игра II Leetcode

Ще броим всеки символ във входния низ и ще го съхраняваме в масив. Както вече споменахме, низ, който е палиндром, може да има само един знак, който се появява нечетен брой пъти. Така че изходът ще бъде с един по-малък от броя на символите. След съхраняване на всяка поява на символен низ в масив. След това правим масив, преминаващ от 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

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

Сложност във времето

О (п) където "н" е броят на знаците във входния низ.

Вижте също
Намерете най-добрите K (или най-често срещаните) числа в поток

Сложност на пространството

O (1), защото създадохме допълнителен масив с постоянен размер. Така космическата сложност е постоянна.