Рубрики

Минимальные вставки для формирования палиндрома | DP-28

Для заданной строки str задача состоит в том, чтобы найти минимальное количество вставляемых символов для преобразования ее в палиндром.

Прежде чем идти дальше, давайте разберемся с несколькими примерами:

  • ab: количество необходимых вставок равно 1, т.е. b ab
  • aa: необходимое количество вставок равно 0, т.е.
  • abcd: необходимое количество вставок — 3, т.е. dcb abcd
  • abcda: Требуемое количество вставок равно 2, т. е. значение bcda постоянного тока совпадает с количеством вставок в подстроке bcd (почему?).
  • abcde: требуется 4 вставки, т.е. edcb abcde

Пусть входная строка будет str [l …… h] . Проблема может быть разбита на три части:

  1. Найдите минимальное количество вставок в подстроке str [l + 1, …… .h].
  2. Найдите минимальное количество вставок в подстроке str [l …… .h-1].
  3. Найдите минимальное количество вставок в подстроке str [l + 1 …… h-1].

Рекурсивный подход : минимальное количество вставок в строку str [l… ..h] может быть задано как:

  • minInsertions (str [l + 1… ..h-1]), если str [l] равен str [h]
  • min (minInsertions (str [l… ..h-1]), minInsertions (str [l + 1… ..h])) + 1 в противном случае

Ниже приведена реализация вышеуказанного подхода:

C ++

// Наивная рекурсивная программа для поиска минимума
// число вставок, необходимое для создания строки
// палиндром
#include<bits/stdc++.h>

using namespace std;

  

  
// Рекурсивная функция для поиска
// минимальное количество вставок

int findMinInsertions(char str[], int l, int h)

{

    // Базовые случаи

    if (l > h) return INT_MAX;

    if (l == h) return 0;

    if (l == h - 1) return (str[l] == str[h])? 0 : 1;

  

    // Проверяем, являются ли первый и последний символы

    // одна и та же. На основании результата сравнения

    // решаем, какие подзадачи нужно вызвать

    return (str[l] == str[h])? 

                    findMinInsertions(str, l + 1, h - 1):

                    (min(findMinInsertions(str, l, h - 1),

                    findMinInsertions(str, l + 1, h)) + 1);

}

  
// Код драйвера

int main()

{

    char str[] = "geeks";

    cout << findMinInsertions(str, 0, strlen(str) - 1);

    return 0;

}

  
// Этот код предоставлен
// Akanksha Rai

С

// Наивная рекурсивная программа для поиска минимума
// число вставок, необходимое для создания строки
// палиндром
#include <stdio.h>
#include <limits.h>
#include <string.h>

  
// Полезная функция для поиска минимум двух чисел

int min(int a, int b)

return a < b ? a : b; }

  
// Рекурсивная функция для поиска минимального числа
// вставки

int findMinInsertions(char str[], int l, int h)

{

    // Базовые случаи

    if (l > h) return INT_MAX;

    if (l == h) return 0;

    if (l == h - 1) return (str[l] == str[h])? 0 : 1;

  

    // Проверяем, являются ли первый и последний символы

    // одна и та же. На основании результата сравнения

    // решаем, какие подзадачи нужно вызвать

    return (str[l] == str[h])? 

                     findMinInsertions(str, l + 1, h - 1):

                     (min(findMinInsertions(str, l, h - 1),

                     findMinInsertions(str, l + 1, h)) + 1);

}

  
// Программа драйвера для проверки вышеуказанных функций

int main()

{

    char str[] = "geeks";

    printf("%d", findMinInsertions(str, 0, strlen(str)-1));

    return 0;

}

Джава

// Наивная рекурсивная Java-программа для поиска минимума
// число вставок, необходимое для создания строки
// палиндром

class GFG {

  

    // Рекурсивная функция для поиска минимального числа

    // вставок

    static int findMinInsertions(char str[], int l,

                                             int h)

    {

        // Базовые случаи

        if (l > h) return Integer.MAX_VALUE;

        if (l == h) return 0;

        if (l == h - 1) return (str[l] == str[h])? 0 : 1;

  

        // Проверяем, есть ли первый и последний символы

        // одинаковы На основании сравнения

        // результат, решить, какую подзадачу (и) вызывать

        return (str[l] == str[h])?

            findMinInsertions(str, l + 1, h - 1):

            (Integer.min(findMinInsertions(str, l, h - 1),

            findMinInsertions(str, l + 1, h)) + 1);

    }

  

    // Программа драйвера для проверки вышеуказанных функций

    public static void main(String args[])

    {

        String str= "geeks";

        System.out.println(findMinInsertions(str.toCharArray(),

                                          0, str.length()-1));

    }

}
// Этот код предоставлен Sumit Ghosh

Python 3

# Наивная рекурсивная программа, чтобы найти минимум
# число вставок, необходимых для создания строки
# палиндром

import sys

  
# Рекурсивная функция для поиска минимума
# количество вставок

def findMinInsertions(str, l, h):

  

    # Базовые случаи

    if (l > h):

        return sys.maxsize

    if (l == h):

        return 0

    if (l == h - 1):

        return 0 if(str[l] == str[h]) else 1

  

    # Проверьте, если первый и последний символы

    # одна и та же. На основании результата сравнения

    # решить, какие подзадачи нужно назвать

      

    if(str[l] == str[h]):

        return findMinInsertions(str, l + 1, h - 1)

    else:

        return (min(findMinInsertions(str, l, h - 1),

                    findMinInsertions(str, l + 1, h)) + 1)

  
Код водителя

if __name__ == "__main__":

      

    str = "geeks"

    print(findMinInsertions(str, 0, len(str) - 1))

  
# Этот код предоставлен ita_c

C #

// Наивная рекурсивная программа на C #
// найти минимальное число
// вставки, необходимые для
// строка палиндром

using System;

  

class GFG

{

    // Рекурсивная функция для

    // найти минимальное количество

    // вставки

    static int findMinInsertions(char []str, 

                                 int l, int h)

    {

        // Базовые случаи

        if (l > h) return int.MaxValue;

        if (l == h) return 0;

        if (l == h - 1) 

            return (str[l] == str[h])? 0 : 1;

  

        // Проверить, если первый и

        // последние символы одинаковы.

        // На основании

        // результат сравнения, решаем

        // какую подзадачу (и) вызывать

        return (str[l] == str[h])?

                findMinInsertions(str, 

                                  l + 1, h - 1):

                (Math.Min(findMinInsertions(str, l, 

                                            h - 1),

                          findMinInsertions(str, l + 

                                        1, h)) + 1);

    

      

    // Код драйвера

    public static void Main()

    {

        string str= "geeks";

        Console.WriteLine(findMinInsertions(str.ToCharArray(),

                                            0, str.Length - 1)); 

    }

}

  
// Этот код предоставлен Sam007


Выход:

3

Решение на основе динамического программирования
Если мы внимательно наблюдаем вышеупомянутый подход, мы можем обнаружить, что он имеет перекрывающиеся подзадачи .
Предположим, мы хотим найти минимальное количество вставок в строку «abcde»:

                      abcde
            /       |      \
           /        |        \
           bcde         abcd       bcd  <- case 3 is discarded as str[l] != str[h]
       /   |   \       /   |   \
      /    |    \     /    |    \
     cde   bcd  cd   bcd abc bc
   / | \  / | \ /|\ / | \
de cd d cd bc c………………….

Подстроки, выделенные полужирным шрифтом, показывают, что рекурсия, которая должна быть завершена, и дерево рекурсии не могут происходить оттуда. Подстрока того же цвета указывает на перекрывающиеся подзадачи .

Как повторно использовать решения подзадач? Техника мемоизации используется, чтобы избежать подобных возвратов подзадачи. Мы можем создать таблицу для хранения результатов подзадач, чтобы их можно было использовать напрямую, если та же самая подзадача встретится снова.

В приведенной ниже таблице представлены сохраненные значения для строки abcde.

a b c d e
----------
0 1 2 3 4
0 0 1 2 3 
0 0 0 1 2 
0 0 0 0 1 
0 0 0 0 0

Как заполнить таблицу?
Стол должен быть заполнен по диагонали. Для строки abcde, 0… .4, должен быть следующий порядок заполнения таблицы:

Gap = 1: (0, 1) (1, 2) (2, 3) (3, 4)

Gap = 2: (0, 2) (1, 3) (2, 4)

Gap = 3: (0, 3) (1, 4)

Gap = 4: (0, 4)

Ниже приведена реализация вышеуказанного подхода:

C ++

// Программа на основе динамического программирования для поиска
// минимальное количество вставок, необходимое для
// строка палиндрома
#include <bits/stdc++.h>

using namespace std;

  

  
// Функция DP для нахождения минимума
// количество вставок

int findMinInsertionsDP(char str[], int n) 

    // Создаем таблицу размером n * n. Таблица [I] [J]

    // будет хранить минимальное количество вставок

    // необходимо преобразовать str [i..j] в палиндром.

    int table[n][n], l, h, gap; 

  

    // Инициализируем все записи таблицы как 0

    memset(table, 0, sizeof(table)); 

  

    // Заполнить таблицу

    for (gap = 1; gap < n; ++gap) 

        for (l = 0, h = gap; h < n; ++l, ++h) 

            table[l][h] = (str[l] == str[h])? 

                        table[l + 1][h - 1] : 

                        (min(table[l][h - 1], 

                             table[l + 1][h]) + 1); 

  

    // Возвращаем минимальное количество вставок

    // для строки [0..n-1]

    return table[0][n - 1]; 

  
// Код драйвера

int main() 

    char str[] = "geeks"

    cout << findMinInsertionsDP(str, strlen(str)); 

    return 0; 

  
// Это код, предоставленный rathbhupendra

С

// Программа на основе динамического программирования для поиска
// минимальное количество вставок, необходимое для
// строка палиндрома
#include <stdio.h>
#include <string.h>

  
// Полезная функция для поиска минимум двух целых чисел

int min(int a, int b)

{   return a < b ? a : b;  }

  
// Функция DP для поиска минимального количества вставок

int findMinInsertionsDP(char str[], int n)

{

    // Создаем таблицу размером n * n. Таблица [I] [J]

    // будет хранить минимальное количество вставок

    // необходимо преобразовать str [i..j] в палиндром.

    int table[n][n], l, h, gap;

  

    // Инициализируем все записи таблицы как 0

    memset(table, 0, sizeof(table));

  

    // Заполнить таблицу

    for (gap = 1; gap < n; ++gap)

        for (l = 0, h = gap; h < n; ++l, ++h)

            table[l][h] = (str[l] == str[h])?

                          table[l+1][h-1] :

                          (min(table[l][h-1], 

                           table[l+1][h]) + 1);

  

    // Возвращаем минимальное количество вставок для

    // str [0..n-1]

    return table[0][n-1];

}

  
// Программа драйвера для проверки вышеуказанной функции.

int main()

{

    char str[] = "geeks";

    printf("%d", findMinInsertionsDP(str, strlen(str)));

    return 0;

}

Джава

// Java-решение для динамического программирования
// основанная программа для поиска минимального числа
// вставки, необходимые для создания строки
// палиндром

import java.util.Arrays;

  

class GFG

{

    // Функция DP для поиска минимального числа

    // вставок

    static int findMinInsertionsDP(char str[], int n)

    {

        // Создаем таблицу размером n * n. Таблица [I] [J]

        // будет хранить минимальное количество вставок

        // необходимо преобразовать str [i..j] в палиндром.

        int table[][] = new int[n][n];

        int l, h, gap;

  

        // Заполнить таблицу

        for (gap = 1; gap < n; ++gap)

        for (l = 0, h = gap; h < n; ++l, ++h)

            table[l][h] = (str[l] == str[h])?

                           table[l+1][h-1] :

                          (Integer.min(table[l][h-1],

                                 table[l+1][h]) + 1);

  

        // Возвращаем минимальное количество вставок

        // для строки [0..n-1]

        return table[0][n-1];

    }

  

    // Программа драйвера для проверки вышеуказанной функции.

    public static void main(String args[])

    {

        String str = "geeks";

        System.out.println(

        findMinInsertionsDP(str.toCharArray(), str.length()));

    }

}
// Этот код предоставлен Sumit Ghosh

python3

# Программа на основе динамического программирования для
# найти минимальное количество необходимых вставок
# сделать стоячий палиндром

  
# Полезная функция для поиска минимума
# из двух целых

def Min(a, b):

    return min(a, b)

  
# Функция DP для поиска минимального числа
Количество вставок

def findMinInsertionsDP(str1, n):

  

    # Создать таблицу размером n * n. Таблица [I] [J]

    # будет хранить минимальное количество вставок

    # необходимо преобразовать str1 [i..j] в палиндром.

    table = [[0 for i in range(n)] 

                for i in range(n)]

    l, h, gap = 0, 0, 0

  

    # Заполните таблицу

    for gap in range(1, n):

        l = 0

        for h in range(gap, n):

            if str1[l] == str1[h]:

                table[l][h] = table[l + 1][h - 1]

            else:

                table[l][h] = (Min(table[l][h - 1], 

                                   table[l + 1][h]) + 1)

            l += 1

  

    # Вернуть минимальное количество вставок

    # для str1 [0..n-1]

    return table[0][n - 1];

  
Код водителя

str1 = "geeks"

print(findMinInsertionsDP(str1, len(str1)))

  
# Этот код предоставлен
# Мохит Кумар 29

C #

// AC # решение для динамического программирования
// основанная программа для поиска минимального числа
// вставки, необходимые для создания строки
// палиндром

using System;

  

class GFG

{

    // Функция DP для поиска минимального числа

    // вставок

    static int findMinInsertionsDP(char []str, int n)

    {

        // Создаем таблицу размером n * n. Таблица [I] [J]

        // будет хранить минимальное количество вставок

        // необходимо преобразовать str [i..j] в палиндром.

        int [,]table = new int[n, n];

        int l, h, gap;

  

        // Заполнить таблицу

        for (gap = 1; gap < n; ++gap)

        for (l = 0, h = gap; h < n; ++l, ++h)

            table[l, h] = (str[l] == str[h])?

                        table[l+1, h-1] :

                        (Math.Min(table[l, h-1],

                                table[l+1, h]) + 1);

  

        // Возвращаем минимальное количество вставок

        // для строки [0..n-1]

        return table[0, n-1];

    }

  

    // Код драйвера

    public static void Main()

    {

        String str = "geeks";

        Console.Write(

        findMinInsertionsDP(str.ToCharArray(), str.Length));

    }

}

  
// Этот код предоставлен Rajput-Ji


Выход:

3

Сложность времени: O (N ^ 2)
Вспомогательное пространство: O (N ^ 2)

Другое решение для динамического программирования (вариация самой длинной общей проблемы подпоследовательности)
Проблема нахождения минимальных вставок также может быть решена с помощью задачи Longest Common Subsequence (LCS) . Если мы обнаружим LCS строки и ее обратное, мы узнаем, сколько максимальных символов может образовать палиндром. Нам нужно вставить оставшиеся символы. Ниже приведены шаги.

  1. Найти длину LCS входной строки и ее обратное. Пусть длина будет «л».
  2. Минимальное количество необходимых вставок — длина входной строки минус «l».

Ниже приведена реализация вышеуказанного подхода:

C ++

// Программа на основе LCS для поиска минимального числа
// вставки, необходимые для создания строки палиндрома
#include <bits/stdc++.h>

using namespace std;

   

  
// Возвращает длину LCS для X [0..m-1], Y [0..n-1].

int lcs( string X, string Y, int m, int n ) 

    int L[n+1][n+1]; 

    int i, j; 

      

    / * Следуя шагам, строим L [m + 1] [n + 1] внизу

        до моды. Обратите внимание, что L [i] [j] содержит длину

        LCS из X [0..i-1] и Y [0..j-1] * /

    for (i = 0; i <= m; i++) 

    

        for (j = 0; j <= n; j++) 

        

        if (i == 0 || j == 0) 

            L[i][j] = 0; 

      

        else if (X[i - 1] == Y[j - 1]) 

            L[i][j] = L[i - 1][j - 1] + 1; 

      

        else

            L[i][j] = max(L[i - 1][j], L[i][j - 1]); 

        

    

      

    / * L [m] [n] содержит длину LCS для X [0..n-1]

        и Y [0..m-1] * /

    return L[m][n]; 

  

void reverseStr(string& str) 

    int n = str.length(); 

  

    // Меняем местами символы, начиная с двух

    // углы

    for (int i = 0; i < n / 2; i++) 

        swap(str[i], str[n - i - 1]); 

  
// основанная на LCS функция, чтобы найти минимальное количество
// вставки

int findMinInsertionsLCS(string str, int n) 

    // Создаем другую строку для хранения обратного 'str'

    string rev = ""

    rev = str; 

    reverseStr(rev); 

      

    // Выводим длину строки минус длина lcs

    // ул и обратный

    return (n - lcs(str, rev, n, n)); 

  
// Код драйвера

int main() 

    string str = "geeks"

    cout << findMinInsertionsLCS(str, str.length()); 

    return 0; 

  
// Этот код предоставлен rathbhupendra

С

// Программа на основе LCS для поиска минимального числа
// вставки, необходимые для создания строки палиндрома
#include<stdio.h>
#include <string.h>

  
/ * Функция полезности для получения максимум 2 целых чисел * /

int max(int a, int b)

{   return (a > b)? a : b; }

  
/ * Возвращает длину LCS для X [0..m-1], Y [0..n-1].

   Смотрите http://goo.gl/bHQVP для подробностей этого

   функция * /

int lcs( char *X, char *Y, int m, int n )

{

   int L[n+1][n+1];

   int i, j;

  

   / * Следуя шагам, строим L [m + 1] [n + 1] внизу

      до моды. Обратите внимание, что L [i] [j] содержит длину

      LCS из X [0..i-1] и Y [0..j-1] * /

   for (i=0; i<=m; i++)

   {

     for (j=0; j<=n; j++)

     {

       if (i == 0 || j == 0)

         L[i][j] = 0;

  

       else if (X[i-1] == Y[j-1])

         L[i][j] = L[i-1][j-1] + 1;

  

       else

         L[i][j] = max(L[i-1][j], L[i][j-1]);

     }

   }

  

   / * L [m] [n] содержит длину LCS для X [0..n-1]

     и Y [0..m-1] * /

   return L[m][n];

}

  
// основанная на LCS функция, чтобы найти минимальное количество
// вставки

int findMinInsertionsLCS(char str[], int n)

{

   // Создаем другую строку для хранения обратного 'str'

   char rev[n+1];

   strcpy(rev, str);

   strrev(rev);

  

   // Выводим длину строки минус длина lcs

   // ул и обратный

   return (n - lcs(str, rev, n, n));

}

  
// Программа драйвера для проверки вышеуказанных функций

int main()

{

    char str[] = "geeks";

    printf("%d", findMinInsertionsLCS(str, strlen(str)));

    return 0;

}

Джава

// Java-программа на основе LCS, чтобы найти минимум
// число вставок, необходимое для создания строки
// палиндром

class GFG

{

    / * Возвращает длину LCS для X [0..m-1],

       Y [0..n-1]. Смотрите http://goo.gl/bHQVP для

       детали этой функции * /

    static int lcs( String X, String Y, int m, int n )

    {

        int L[][] = new int[n+1][n+1];

        int i, j;

  

        / * Следуя шагам, строим L [m + 1] [n + 1] в

           снизу вверх мода. Обратите внимание, что L [i] [j]

           содержит длину LCS X [0..i-1]

           и Y [0..j-1] * /

        for (i=0; i<=m; i++)

        {

            for (j=0; j<=n; j++)

            {

                if (i == 0 || j == 0)

                    L[i][j] = 0;

  

                else if (X.charAt(i-1) == Y.charAt(j-1))

                    L[i][j] = L[i-1][j-1] + 1;

  

                else

                    L[i][j] = Integer.max(L[i-1][j], L[i][j-1]);

            }

        }

  

        / * L [m] [n] содержит длину LCS для

           Х [0..n-1] и Y [0..m-1] * /

        return L[m][n];

    }

  

    // функция на основе LCS для поиска минимального числа

    // вставок

    static int findMinInsertionsLCS(String str, int n)

    {

        // Использование StringBuffer для обращения строки

        StringBuffer sb = new StringBuffer(str);

        sb.reverse();

        String revString = sb.toString();

  

        // Выводим длину строки минус

        // длина lcs из str и обратная

        return (n - lcs(str, revString , n, n));

    }

  

    // Программа драйвера для проверки вышеуказанных функций

    public static void main(String args[])

    {

        String str = "geeks";

        System.out.println(

        findMinInsertionsLCS(str, str.length()));

    }

}
// Этот код предоставлен Sumit Ghosh

C #

// Программа на C # на основе LCS для нахождения минимума
// число вставок, необходимое для создания строки
// палиндром

using System;

  

class GFG

{

    / * Возвращает длину LCS для X [0..m-1],

    Y [0..n-1]. Смотрите http://goo.gl/bHQVP для

    детали этой функции * /

    static int lcs( string X, string Y, int m, int n )

    {

        int[,] L = new int[n + 1, n + 1];

        int i, j;

  

        / * Следуя шагам, строим L [m + 1, n + 1] в

        снизу вверх мода. Обратите внимание, что L [i, j]

        содержит длину LCS X [0..i-1]

        и Y [0..j-1] * /

        for (i = 0; i <= m; i++)

        {

            for (j = 0; j <= n; j++)

            {

                if (i == 0 || j == 0)

                    L[i, j] = 0;

  

                else if (X[i - 1] == Y[j - 1])

                    L[i, j] = L[i - 1, j - 1] + 1;

  

                else

                    L[i, j] = Math.Max(L[i - 1, j], L[i, j - 1]);

            }

        }

  

        / * L [m, n] содержит длину LCS для

        Х [0..n-1] и Y [0..m-1] * /

        return L[m,n];

    }

  

    // функция на основе LCS для поиска минимального числа

    // вставок

    static int findMinInsertionsLCS(string str, int n)

    {

        // Использование charArray для обращения строки

        char[] charArray = str.ToCharArray();

        Array.Reverse(charArray);

        string revString = new string(charArray);

  

        // Выводим длину строки минус

        // длина lcs из str и обратная

        return (n - lcs(str, revString , n, n));

    }

  

    // Код драйвера

    static void Main()

    {

        string str = "geeks";

        Console.WriteLine(findMinInsertionsLCS(str,str.Length));

    }

}

  
// Этот код предоставлен mits


Выход:

3


Сложность времени:
O (N ^ 2)
Вспомогательное пространство : O (N ^ 2)

Связанная статья:
Минимальное количество аппендов, необходимых для создания струнного палиндрома

Эта статья составлена Aashish Barnwal . Пожалуйста, напишите комментарии, если вы обнаружите что-то неправильное, или вы хотите поделиться дополнительной информацией по обсуждаемой выше теме.

Рекомендуемые посты:

Минимальные вставки для формирования палиндрома | DP-28

0.00 (0%) 0 votes