Допускається мінімум вставок для формування паліндрому з перестановками


Рівень складності Medium
Часто запитують у Амазонка CodeNation Directi Google Дійсно Осягати інтуїтивно
Динамічне програмування рядок

Проблема "Мінімальне вставлення для формування паліндрому з дозволеними перестановками" стверджує, що вам дається рядок із усіма літерами в нижньому регістрі. Постановка проблеми вимагає з'ясувати мінімальну вставку символу в рядок, який може стати Паліндромом. Положення символів можна змінювати в рядку.

Приклад

Допускається мінімум вставок для формування паліндрому з перестановками

malyalam
1

Пояснення

Якщо ми можемо додати 'a' до початкового рядка, ми можемо створити паліндром.

madaam
1

Пояснення

Або додайте "d" або "a", щоб зробити оригінальний рядок паліндром.

Алгоритм

  1. Встановіть довжину рядка на l і вивести на 0.
  2. Заявіть ціле масив.
  3. Зберігайте та підтримуйте кількість кожного символу в рядку.
  4. Перемістіть масив, починаючи від 0 до, поки i <26.
    1. Перевірте, чи є countChar [i] % 2 == 1,
      1. Якщо true, тоді виконайте вивід ++.
  5. Якщо вихідний результат дорівнює 0, поверніть 0.
  6. Інший вихідний результат-1.

Пояснення

Вам дано a рядок, ваше завдання - визначити мінімальну вставку, яка повинна бути зроблена в рядку, щоб він став паліндромом. Положення символів можна змінювати в рядку. Ми підрахуємо входження символу рядка і збережемо його в масиві. Оскільки ідея полягає в тому, що коли рядок є паліндромом, існує лише один символ, який може бути непарним, коли довжина рядка непарна. Крім цього всі символи мають рівну частоту. Тож нам потрібно знайти символи, які трапляються непарну кількість разів.

Ми підрахуємо кожен символ у вхідному рядку і збережемо його в масиві. Як ми вже згадували, рядок, який є паліндромом, може мати лише один символ, який трапляється непарна кількість разів. Тож результат буде на один менше, ніж кількість символів. Після збереження кожного масиву рядка символів у масиві. Потім ми робимо масив, що переходить від i = 0 до i, менше 26. Це пояснюється тим, що в цілому 26 символів, і ми повинні припустити, що існує ймовірність появи 26 символів у даному рядку.

Під час обходу масиву ми перевіримо, якщо ділення кожного рахунку на 2 залишає залишок 1, якщо це істина, тоді це збільшить кількість вихідних даних на 1 (вихід ++). Після обходу масиву, якщо count залишається нулем, це означає, що ми не знайдемо нічого в символі, що є непарним, означає, що рядок вже є паліндромом, ми повернемо 0, інакше ми повернемо (output-1), оскільки ми вже згадали, вихід буде на один менше, ніж кількість символів і, отже, ми отримали результат.

код

Код С ++ для пошуку Мінімальних вставок для формування паліндрому з дозволеними перестановками

#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

Аналіз складності

Складність часу

О (п) де "N" - кількість символів у вхідному рядку.

Складність простору

O (1), тому що ми створили додатковий масив, що має постійний розмір. Таким чином, космічна складність постійна.