Минимум вставок для формирования палиндрома с допустимыми перестановками


Сложный уровень средний
Часто спрашивают в Амазонка CodeNation Directi Google В самом деле Постигать интуитивно
Динамическое программирование строка

Задача «Минимальные вставки для формирования палиндрома с разрешенными перестановками» гласит, что вам дана строка со всеми буквами в нижнем регистре. В постановке задачи предлагается определить минимальный размер вставки символа в строку, который может стать палиндромом. Положение символов в строке можно изменить.

Пример

Минимум вставок для формирования палиндрома с допустимыми перестановками

malyalam
1

объяснение

Если мы можем добавить «а» к начальной строке, мы можем создать палиндром.

madaam
1

объяснение

Добавьте «d» или «a», чтобы получился исходный палиндром строки.

Алгоритм

  1. Установите длину строки равной l и вывести на 0.
  2. Объявить целое массив.
  3. Храните и поддерживайте счетчик каждого символа в строке.
  4. Пройдите по массиву, начиная с 0 до i <26.
    1. Проверить, если countChar [i] % 2 == 1,
      1. Если true, то вывести ++.
  5. Если вывод равен 0, вернуть 0.
  6. Иначе возвратите output-1.

объяснение

Вам дается строка, ваша задача - найти минимальную вставку в строку, чтобы она стала палиндромом. Положение символов в строке можно изменить. Мы собираемся подсчитать появление символа строки и сохранить его в массиве. Потому что идея заключается в том, что когда строка является палиндромом, есть только один символ, который может быть нечетным, если длина строки нечетная. В остальном все символы имеют одинаковую частоту. Итак, нам нужно найти символы, которые встречаются нечетное количество раз.

Мы собираемся подсчитать каждый символ во входной строке и сохранить его в массиве. Как мы уже упоминали, строка, которая является палиндромом, может иметь только один символ, который встречается нечетное количество раз. Таким образом, результат будет на единицу меньше, чем количество символов. После сохранения каждого вхождения символьной строки в массив. Затем мы делаем обход массива от i = 0 до i меньше 26. Это потому, что всего 26 символов, и мы должны предположить, что вероятность появления 26 символов в данной строке.

При обходе массива мы проверяем, дает ли деление каждого счетчика на 2 остаток 1, если он истинен, тогда он увеличит счетчик вывода на 1 (вывод ++). После обхода массива, если count остается равным нулю, означает, что мы не находим ничего в символе, что является нечетным, означает, что строка уже является палиндромом, мы вернем 0, иначе мы вернем (output-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), потому что мы создали дополнительный массив постоянного размера. Таким образом, сложность пространства постоянна.