Рубрики

Минимальное количество удалений для создания строки палиндрома

Дана строка размером 'n'. Задача состоит в том, чтобы удалить или удалить минимальное количество символов из строки, чтобы полученная строка была палиндромом.

Примечание: порядок символов должен быть сохранен.

Примеры :

Input : aebcbda
Output : 2
Remove characters 'e' and 'd'
Resultant string will be 'abcba'
which is a palindromic string

Input : geeksforgeeks
Output : 8

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

Эффективный подход использует концепцию нахождения длины самой длинной палиндромной подпоследовательности данной последовательности.

Алгоритм:

-->str is the given string.
-->n length of str
-->len be the length of the longest 
   palindromic subsequence of str
-->// minimum number of deletions 
   min = n - len

C ++

// реализация C ++ для поиска
// минимальное количество удалений
// сделать строку палиндромной
#include <bits/stdc++.h>

using namespace std;

  
// Возвращает длину
// самый длинный палиндром
// подпоследовательность в 'str'

int lps(string str)

{

    int n = str.size();

  

    // Создать таблицу для хранения

    // результаты подзадач

    int L[n][n];

  

    // Строки длины 1

    // палиндром длины 1

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

        L[i][i] = 1;

  

    // Построить таблицу. Обратите внимание, что

    // нижние значения диагонали

    // таблицы бесполезны и

    // не заполнен в процессе.

    // c1 - длина подстроки

    for (int cl = 2; cl <= n; cl++)

    {

        for (int i = 0; 

                 i < n - cl + 1; i++)

        {

            int j = i + cl - 1;

            if (str[i] == str[j] &&

                        cl == 2)

                L[i][j] = 2;

            else if (str[i] == str[j])

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

            else

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

                            L[i + 1][j]);

        }

    }

  

    // длина самого длинного

    // палиндромная последовательность

    return L[0][n - 1];

}

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

int minimumNumberOfDeletions(string str)

{

    int n = str.size();

  

    // Находим самый длинный палиндром

    // подпоследовательность

    int len = lps(str);

  

    // После удаления символов

    // кроме lps, мы

    // получить палиндром.

    return (n - len);

}

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

int main()

{

    string str = "geeksforgeeks";

    cout << "Minimum number of deletions = "

         << minimumNumberOfDeletions(str);

    return 0;

}

Джава

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

class GFG

{

    // Возвращает длину

    // самый длинный палиндром

    // подпоследовательность в 'str'

    static int lps(String str)

    {

        int n = str.length();

  

        // Создать таблицу для хранения

        // результаты подзадач

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

  

        // Строки длины 1

        // палиндром длины 1

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

            L[i][i] = 1;

  

        // Построить таблицу. Заметка

        // нижняя диагональ

        // значения таблицы бесполезны

        // и не заполнен в процессе.

        // c1 - длина подстроки

        for (int cl = 2; cl <= n; cl++)

        {

            for (int i = 0; i < n - cl + 1; i++)

            {

                int j = i + cl - 1;

                if (str.charAt(i) == 

                        str.charAt(j) && cl == 2)

                    L[i][j] = 2;

                else if (str.charAt(i) == 

                              str.charAt(j))

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

                else

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

                                         L[i + 1][j]);

            }

        }

  

        // длина самого длинного

        // палиндромная подпоследовательность

        return L[0][n - 1];

    }

  

    // функция для расчета минимума

    // количество удалений

    static int minimumNumberOfDeletions(String str)

    {

        int n = str.length();

  

        // Находим самый длинный палиндром

        // подпоследовательность

        int len = lps(str);

  

        // После удаления символов

        // кроме lps получаем

        // палиндром.

        return (n - len);

    }

  

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

    public static void main(String[] args)

    {

        String str = "geeksforgeeks";

        System.out.println("Minimum number "

                            "of deletions = "

               minimumNumberOfDeletions(str));

    }

}

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

Python 3

# Реализация Python 3 для поиска
# минимальное количество удалений
# сделать строку палиндромной

   
# Возвращает длину
# самый длинный палиндромик
# подпоследовательность в 'str'

def lps(str):

    n = len(str)

   

    # Создать таблицу для хранения

    # результаты подзадач

    L = [[0 for x in range(n)]for y in range(n)]

   

    # Строки длиной 1

    # палиндром длины 1

    for i in range(n):

        L[i][i] = 1

   

    Построить стол. Обратите внимание, что

    # нижние значения диагонали

    # таблицы бесполезны и

    # не заполнено в процессе.

    # c1 - длина подстроки

    for cl in range( 2, n+1):

        for i in range(n - cl + 1):

            j = i + cl - 1

            if (str[i] == str[j] and cl == 2):

                L[i][j] = 2

            elif (str[i] == str[j]):

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

            else:

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

   

    # длина самого длинного

    # palindromic subseq

    return L[0][n - 1]

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

def minimumNumberOfDeletions( str):

  

    n = len(str)

   

    # Найти самый длинный палиндром

    # подпоследовательность

    l = lps(str)

   

    # После удаления символов

    # кроме ЛПС мы

    # получить палиндром.

    return (n - l)

   
Код водителя

if __name__ == "__main__":

      

    str = "geeksforgeeks"

    print( "Minimum number of deletions = "

         , minimumNumberOfDeletions(str))

C #

// реализация C # для поиска
// минимальное количество удалений
// сделать строку палиндромной

using System;

  

class GFG

{

    // Возвращает длину

    // самый длинный палиндром

    // подпоследовательность в 'str'

    static int lps(String str)

    {

        int n = str.Length;

  

        // Создать таблицу для хранения

        // результаты подзадач

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

  

        // Строки длины 1

        // палиндром длины 1

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

            L[i, i] = 1;

  

        // Построить таблицу. Заметка

        // нижняя диагональ

        // значения таблицы бесполезны

        // и не заполнен в процессе.

        // c1 - длина подстроки

        for (int cl = 2; cl <= n; cl++)

        {

            for (int i = 0; i < n - cl + 1; i++)

            {

                int j = i + cl - 1;

                if (str[i] == str[j] && cl == 2)

                    L[i, j] = 2;

                else if (str[i] == str[j])

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

                else

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

                                      L[i + 1, j]);

            }

        }

  

        // длина самого длинного

        // палиндромная подпоследовательность

        return L[0, n - 1];

    }

  

    // функция для расчета минимума

    // количество удалений

    static int minimumNumberOfDeletions(string str)

    {

        int n = str.Length;

  

        // Находим самый длинный палиндром

        // подпоследовательность

        int len = lps(str);

  

        // После удаления символов

        // кроме lps получаем

        // палиндром.

        return (n - len);

    }

  

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

    public static void Main()

    {

        string str = "geeksforgeeks";

        Console.Write("Minimum number of" +

                          " deletions = "

            minimumNumberOfDeletions(str));

    }

}

  
// Этот код предоставлен нитин митталь.

PHP

<?php
// Реализация PHP для поиска
// минимальное количество удалений
// сделать строку палиндромной

  
// Возвращает длину
// самый длинный палиндром
// подпоследовательность в 'str'

function lps($str)

{

    $n = strlen($str);

  

    // Создать таблицу для хранения

    // результаты подзадач

    $L;

  

    // Строки длины 1

    // палиндром длины 1

    for ($i = 0; $i < $n; $i++)

        $L[$i][$i] = 1;

  

    // Построить таблицу. Обратите внимание, что

    // нижние значения диагонали

    // таблицы бесполезны и

    // не заполнен в процессе.

    // c1 - длина подстроки

    for ($cl = 2; $cl <= $n; $cl++)

    {

        for ( $i = 0;

              $i < $n -$cl + 1; 

              $i++)

        {

            $j = $i + $cl - 1;

            if ($str[$i] == $str[$j] && 

                            $cl == 2)

                $L[$i][$j] = 2;

            else if ($str[$i] == $str[$j])

                $L[$i][$j] = 

                        $L[$i + 1][$j - 1] + 2;

              

            else

                $L[$i][$j] = max($L[$i][$j - 1], 

                                $L[$i + 1][$j]);

        }

    }

  

    // длина самого длинного

    // палиндромная последовательность

    return $L[0][$n - 1];

}

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

function minimumNumberOfDeletions($str)

{

    $n = strlen($str);

  

    // Найти самый длинный

    // палиндромная подпоследовательность

    $len = lps($str);

  

    // После удаления символов

    // кроме lps получаем

    // палиндром.

    return ($n - $len);

}

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

    $str = "geeksforgeeks";

    echo "Minimum number of deletions = "

           minimumNumberOfDeletions($str);

    return 0;

}

  
// Этот код предоставлен нитин митталь.
?>


Выход :

Minimum number of deletions = 8

Сложность времени: O (n 2 )

Эта статья предоставлена Аюшем Джаухари . Если вы как GeeksforGeeks и хотели бы внести свой вклад, вы также можете написать статью с помощью contribute.geeksforgeeks.org или по почте статьи contribute@geeksforgeeks.org. Смотрите свою статью, появляющуюся на главной странице GeeksforGeeks, и помогите другим вундеркиндам.

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

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

Минимальное количество удалений для создания строки палиндрома

0.00 (0%) 0 votes