Рубрики

Найти, является ли строка K-палиндромом или нет | Комплект 1

По заданной строке выясните, является ли строка K-палиндромом или нет. Строка k-палиндрома превращается в палиндром при удалении из нее не более k символов.

Примеры :

Input : String - abcdecba, k = 1
Output : Yes
String can become palindrome by remo-
-ving 1 character i.e. either d or e)


Input  : String - abcdeca, K = 2
Output : Yes
Can become palindrome by removing
2 characters b and e.

Input : String - acdcb, K = 1
Output : No
String can not become palindrome by
removing only one character.

Если мы тщательно проанализируем проблему, задача состоит в том, чтобы преобразовать данную строку в ее обратную, удалив из нее не более K символов. Проблема в основном в изменении расстояния редактирования . Мы можем изменить задачу «Редактировать расстояние», чтобы рассматривать данную строку и ее обратную сторону в качестве входных данных, и единственной допустимой операцией является удаление. Поскольку данная строка сравнивается с ее обратной, мы сделаем не более N удалений из первой строки и N удалений из второй строки, чтобы сделать их равными. Поэтому, чтобы строка была k-палиндромом, 2 * N <= 2 * K должно выполняться.

Ниже приведены подробные шаги алгоритма —

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

  1. Если последние символы двух строк совпадают, мы игнорируем последние символы и получаем количество оставшихся строк. Таким образом, мы повторяем для длин m-1 и n-1, где m — длина str1, а n — длина str2.
  2. Если последние символы не совпадают, мы рассматриваем операцию удаления последнего символа первой строки и последнего символа второй строки, рекурсивно вычисляем минимальную стоимость операций и принимаем минимум два значения.
    • Удалить последний символ из str1: повторить для m-1 и n.
    • Удалить последний символ из str2: повторить для m и n-1.

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

C ++

// Наивная рекурсивная программа C ++ для поиска
// если данная строка является K-палиндромом или нет
#include<bits/stdc++.h>

using namespace std;

  
// найти, является ли данная строка K-палиндромом или нет

int isKPalRec(string str1, string str2, int m, int n)

{

    // Если первая строка пуста, единственный вариант

    // удаляем все символы второй строки

    if (m == 0) return n;

  

    // Если вторая строка пуста, единственный вариант

    // удаляем все символы первой строки

    if (n == 0) return m;

  

    // Если последние символы двух строк совпадают, игнорировать

    // последние символы и получаем количество оставшихся строк.

    if (str1[m-1] == str2[n-1])

        return isKPalRec(str1, str2, m-1, n-1);

  

    // Если последние символы не совпадают,

    // 1. Удалить последний символ из str1 и повторить для m-1 и n

    // 2. Удалить последний символ из str2 и повторить для m и n-1

    // Взять минимум две вышеуказанные операции

    return 1 + min(isKPalRec(str1, str2, m-1, n), // Удалить из str1

                   isKPalRec(str1, str2, m, n-1)); // Удалить из str2

}

  
// Возвращает true, если str равно k палиндрому.

bool isKPal(string str, int k)

{

    string revStr = str;

    reverse(revStr.begin(), revStr.end());

    int len = str.length();

  

    return (isKPalRec(str, revStr, len, len) <= k*2);

}

  
// Драйвер программы

int main()

{

    string str = "acdcb";

    int k = 2;

    isKPal(str, k)? cout << "Yes" : cout << "No";

    return 0;

}

Джава

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

class GFG 

{

  

    // найти, если данная строка

    // К-палиндром или нет

    static int isKPalRec(String str1, 

            String str2, int m, int n) 

    {

        // Если первая строка пуста,

        // единственный вариант - удалить

        // все символы второй строки

        if (m == 0

        {

            return n;

        }

  

        // Если вторая строка пуста,

        // единственный вариант - удалить

        // все символы первой строки

        if (n == 0

        {

            return m;

        }

  

        // Если последние два символа

        // строки одинаковые, игнорируем

        // последние символы и получаем

        // считать оставшиеся строки.

        if (str1.charAt(m - 1) == 

            str2.charAt(n - 1))

        {

            return isKPalRec(str1, str2, 

                            m - 1, n - 1);

        }

  

        // Если последние символы не совпадают,

        // 1. Удалить последний символ из str1 и

        // повторяем для m-1 и n

        // 2. Удалить последний символ из str2 и

        // повторяем для m и n-1

        // Взять минимум две вышеуказанные операции

        return 1 + Math.min(isKPalRec(str1, str2, m - 1, n), // Удалить из str1

                isKPalRec(str1, str2, m, n - 1)); // Удалить из str2

    }

  

    // Возвращает true, если str равно k палиндрому.

    static boolean isKPal(String str, int k) 

    {

        String revStr = str;

        revStr = reverse(revStr);

        int len = str.length();

  

        return (isKPalRec(str, revStr, len, len) <= k * 2);

    }

  

    static String reverse(String input) 

    {

        char[] temparray = input.toCharArray();

        int left, right = 0;

        right = temparray.length - 1;

  

        for (left = 0; left < right; left++, right--)

        {

            // Меняем значения слева и справа

            char temp = temparray[left];

            temparray[left] = temparray[right];

            temparray[right] = temp;

        }

        return String.valueOf(temparray);

    }

  

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

    public static void main(String[] args)

    {

        String str = "acdcb";

        int k = 2;

        if (isKPal(str, k)) 

        {

            System.out.println("Yes");

        }

        else 

        {

            System.out.println("No");

        }

    }

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

python3

# Наивный рекурсивный Python3
# код, чтобы найти, если задана строка
# К-палиндром или нет

  
# Найти, если задана строка
# К-палиндром или нет

def isKPalRec(str1, str2, m, n):

      

    # Если первая строка пуста,

    # единственный вариант - удалить

    # все символы второй строки

    if not m: return n

  

    # Если вторая строка пуста,

    # единственный вариант - удалить

    # все символы первой строки

    if not n: return m

  

    # Если последние символы двух строк

    # одинаковы, игнорировать последние символы

    # и получить количество оставшихся строк.

    if str1[m-1] == str2[n-1]:

        return isKPalRec(str1, str2, m-1, n-1)

  

    # Если последние символы не совпадают,

    # 1. Удалить последний символ из str1 и повторить для m-1 и n

    # 2. Удалить последний символ из str2 и повторить для m и n-1

    # Взять минимум две вышеуказанные операции

    res = 1 + min(isKPalRec(str1, str2, m-1, n),  # Удалить из str1

                 (isKPalRec(str1, str2, m, n-1))) # Удалить из str2

                   

    return res

  
# Возвращает true, если str равно k палиндрому.

def isKPal(string, k):

    revStr = string[::-1]

    l = len(string)

  

    return (isKPalRec(string, revStr, l, l) <= k * 2)

  

  
# Драйверная программа

string = "acdcb"

k = 2

  

print("Yes" if isKPal(string, k) else "No")

  

  
# Этот код предоставлен Ансу Кумари.

C #

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

using System;

  

class GFG 

  

    // найти, если данная строка

    // К-палиндром или нет

    static int isKPalRec(String str1, 

            String str2, int m, int n) 

    

        // Если первая строка пуста,

        // единственный вариант - удалить

        // все символы второй строки

        if (m == 0) 

        

            return n; 

        

  

        // Если вторая строка пуста,

        // единственный вариант - удалить

        // все символы первой строки

        if (n == 0) 

        

            return m; 

        

  

        // Если последние два символа

        // строки одинаковые, игнорируем

        // последние символы и получаем

        // считать оставшиеся строки.

        if (str1[m - 1] == 

            str2[n - 1]) 

        

            return isKPalRec(str1, str2, 

                            m - 1, n - 1); 

        

  

        // Если последние символы не совпадают,

        // 1. Удалить последний символ из str1 и

        // повторяем для m-1 и n

        // 2. Удалить последний символ из str2 и

        // повторяем для m и n-1

        // Взять минимум две вышеуказанные операции

        return 1 + Math.Min(isKPalRec(str1, str2, m - 1, n), // Удалить из str1

                isKPalRec(str1, str2, m, n - 1)); // Удалить из str2

    

  

    // Возвращает true, если str равно k палиндрому.

    static bool isKPal(String str, int k) 

    

        String revStr = str; 

        revStr = reverse(revStr); 

        int len = str.Length; 

  

        return (isKPalRec(str, revStr, len, len) <= k * 2); 

    

  

    static String reverse(String input) 

    

        char[] temparray = input.ToCharArray(); 

        int left, right = 0; 

        right = temparray.Length - 1; 

  

        for (left = 0; left < right; left++, right--) 

        

            // Меняем значения слева и справа

            char temp = temparray[left]; 

            temparray[left] = temparray[right]; 

            temparray[right] = temp; 

        

        return String.Join("",temparray); 

    

  

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

    public static void Main(String[] args) 

    

        String str = "acdcb"

        int k = 2; 

        if (isKPal(str, k)) 

        

            Console.WriteLine("Yes"); 

        

        else

        

            Console.WriteLine("No"); 

        

    

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


Выход :

Yes

Временная сложность вышеуказанного решения является экспоненциальной. В худшем случае мы можем выполнить O (2 n ) операций. В худшем случае строка содержит все различные символы.

Эта проблема имеет оба свойства (см. Это и это ) задачи динамического программирования. Как и другие типичные проблемы динамического программирования (DP), повторных вычислений тех же подзадач можно избежать, создав временный массив, в котором хранятся результаты подзадач.

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

C ++

// C ++ программа для поиска, является ли данная строка K-палиндромом или нет
#include <bits/stdc++.h>

using namespace std;

  
// найти, является ли данная строка K-палиндромом или нет

int isKPalDP(string str1, string str2, int m, int n)

{

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

    int dp[m + 1][n + 1];

  

    // Заполняем dp [] [] снизу вверх

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

    {

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

        {

            // Если первая строка пуста, единственный вариант

            // удаляем все символы второй строки

            if (i == 0)

                dp[i][j] = j; // Мин. операции = j

  

            // Если вторая строка пуста, единственный вариант -

            // удаляем все символы первой строки

            else if (j == 0)

                dp[i][j] = i; // Мин. операции = я

  

            // Если последние символы совпадают, игнорировать последний символ

            // и повторить оставшуюся строку

            else if (str1[i - 1] == str2[j - 1])

                dp[i][j] = dp[i - 1][j - 1];

  

            // Если последний символ отличается, удалите его

            // и найти минимум

            else

             dp[i][j] = 1 + min(dp[i - 1][j], // Удалить из str1

                             dp[i][j - 1]); // Удалить из str2

        }

    }

  

    return dp[m][n];

}

  
// Возвращает true, если str равно k палиндрому.

bool isKPal(string str, int k)

{

    string revStr = str;

    reverse(revStr.begin(), revStr.end());

    int len = str.length();

  

    return (isKPalDP(str, revStr, len, len) <= k*2);

}

  
// Драйвер программы

int main()

{

    string str = "acdcb";

    int k = 2;

    isKPal(str, k)? cout << "Yes" : cout << "No";

    return 0;

}

Джава

// Java-программа для поиска, если дано
// строка К-палиндром или нет

class GFG 

{

  

    // найти, если данная строка

    // К-палиндром или нет

    static int isKPalDP(String str1, 

            String str2, int m, int n) 

    {

          

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

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

        int dp[][] = new int[m + 1][n + 1];

  

        // Заполняем dp [] [] снизу вверх

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

        {

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

            {

                  

                // Если первая строка пуста,

                // единственный вариант - удалить все

                // символы второй строки

                if (i == 0

                {

                    // Мин. операции = j

                    dp[i][j] = j; 

                

                  

                // Если вторая строка пуста,

                // единственный вариант - удалить все

                // символы первой строки

                else if (j == 0

                {

                    // Мин. операции = я

                    dp[i][j] = i; 

                

                  

                // Если последние символы совпадают,

                // игнорируем последний символ и

                // повторить оставшуюся строку

                else if (str1.charAt(i - 1) ==

                        str2.charAt(j - 1)) 

                {

                    dp[i][j] = dp[i - 1][j - 1];

                

                  

                // Если последний символ отличается,

                // удалить его и найти минимум

                else 

                {

                    // Удалить из str1

                    // Удалить из str2

                    dp[i][j] = 1 + Math.min(dp[i - 1][j], 

                            dp[i][j - 1]); 

                }

            }

        }

        return dp[m][n];

    }

  

    // Возвращает true, если str равно k палиндрому.

    static boolean isKPal(String str, int k)

    {

        String revStr = str;

        revStr = reverse(revStr);

        int len = str.length();

  

        return (isKPalDP(str, revStr,

                len, len) <= k * 2);

    }

  

    static String reverse(String str)

    {

        StringBuilder sb = new StringBuilder(str);

        sb.reverse();

        return sb.toString();

    }

      

    // Драйвер программы

    public static void main(String[] args) 

    {

        String str = "acdcb";

        int k = 2;

        if (isKPal(str, k)) 

        {

            System.out.println("Yes");

        

        else 

        {

            System.out.println("No");

        }

    }

}

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

python3

# Программа Python, чтобы найти, если дано
# строка К-палиндром или нет

  
# Найти, если данная строка
К-палиндром или нет

def isKPalDP(str1, str2, m, n):

      

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

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

    dp = [[0] * (n + 1) for _ in range(m + 1)]

  

    # Заполните дп [] [] снизу вверх

    for i in range(m + 1):

          

        for j in range(n + 1):

              

            # Если первая строка пуста,

            # Единственный вариант - удалить

            # все символы второй строки

            if not i :

                dp[i][j] = j    # Мин. операции = j

  

            # Если вторая строка пуста,

            # Единственный вариант - удалить

            # все символы первой строки

            elif not j :

                dp[i][j] = i    # Мин. операции = я

  

            # Если последние символы совпадают,

            # игнорировать последний символ и

            # recur для оставшейся строки

            elif (str1[i - 1] == str2[j - 1]):

                dp[i][j] = dp[i - 1][j - 1]

  

            # Если последний символ отличается,

            # удали его и найди минимум

            else:

                dp[i][j] = 1 + min(dp[i - 1][j],  # Удалить из str1

                                  (dp[i][j - 1])) # Удалить из str2

  

    return dp[m][n]

  
# Возвращает true если str
# это п палиндром.

def isKPal(string, k):

      

    revStr = string[::-1]

    l = len(string)

      

    return (isKPalDP(string, revStr, l, l) <= k * 2)

  

  
# Драйверная программа

string = "acdcb"

k = 2

print("Yes" if isKPal(string, k) else "No")

  

  
# Этот код предоставлен Ансу Кумари.


Выход :

Yes

Временная сложность вышеуказанного решения составляет O (mxn). Мы можем улучшить временную сложность, используя тот факт, что разрешено только k удалений. Используемое вспомогательное пространство O (mxn).

Найти, является ли строка K-палиндромом или нет | Комплект 2 (Использование LCS)

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

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

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

Найти, является ли строка K-палиндромом или нет | Комплект 1

0.00 (0%) 0 votes