Рубрики

Подсчитать всю палиндромную подпоследовательность в данной строке

Найдите, сколько палиндромных подпоследовательностей (не обязательно должно быть различимым) может быть сформировано в данной строке. Обратите внимание, что пустая строка не считается палиндромом.
Примеры:

Input : str = "abcd"
Output : 4
Explanation :- palindromic  subsequence are : "a" ,"b", "c" ,"d" 

Input : str = "aab"
Output : 4
Explanation :- palindromic subsequence are :"a", "a", "b", "aa"

Input : str = "aaaa"
Output : 15

Вышеуказанная проблема может быть рекурсивно определена.

Initial Values : i= 0, j= n-1;

CountPS(i,j)
// Every single character of a string is a palindrome 
// subsequence 
if i == j
   return 1 // palindrome of length 1

// If first and last characters are same, then we 
// consider it as palindrome subsequence and check
// for the rest subsequence (i+1, j), (i, j-1)
Else if (str[i] == str[j)]
   return   countPS(i+1, j) + countPS(i, j-1) + 1;

else
   // check for rest sub-sequence and  remove common
   // palindromic subsequences as they are counted
   // twice when we do countPS(i+1, j) + countPS(i,j-1)
   return countPS(i+1, j) + countPS(i, j-1) - countPS(i+1, j-1) 

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

C ++

// Подсчитывает палиндромную подпоследовательность в заданной строке
#include<iostream>
#include<cstring>

using namespace std;

  
// Функция, возвращающая общую палиндромную подпоследовательность

int countPS(string str)

{

    int N = str.length();

  

    // создаем 2D массив для хранения счетчика палиндромов

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

    int cps[N+1][N+1];

    memset(cps, 0 ,sizeof(cps));

  

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

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

        cps[i][i] = 1;

  

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

    for (int L=2; L<=N; L++)

    {

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

        {

            int k = L+i-1;

            if (str[i] == str[k])

                cps[i][k] = cps[i][k-1] +

                            cps[i+1][k] + 1;

            else

                cps[i][k] = cps[i][k-1] +

                            cps[i+1][k] -

                            cps[i+1][k-1];

        }

    }

  

    // возвращаем полную палиндромную подпоследовательность

    return cps[0][N-1];

}

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

int main()

{

    string str = "abcb";

    cout << "Total palindromic subsequence are : "

         << countPS(str) << endl;

    return 0;

}

Джава

// Java-код для подсчета палиндромной подпоследовательности
// в заданной строке

public class GFG 

{      

    // Функция возврата общего палиндромного

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

    static int countPS(String str)

    {

        int N = str.length();

       

        // создаем 2D массив для хранения счета

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

        int[][] cps = new int[N+1][N+1];

       

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

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

            cps[i][i] = 1;

       

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

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

        for (int L=2; L<=N; L++)

        {

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

            {

                int k = L + i - 1;

                if (k < N){

                if (str.charAt(i) == str.charAt(k))

                    cps[i][k] = cps[i][k-1] +

                                cps[i+1][k] + 1;

                else

                    cps[i][k] = cps[i][k-1] +

                                cps[i+1][k] -

                                cps[i+1][k-1];

                }

            }

        }

       

        // возвращаем полную палиндромную подпоследовательность

        return cps[0][N-1];

    }

       

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

    public static void main(String args[])

    {

        String str = "abcb";

        System.out.println("Total palindromic "+

                            "subsequence are : "

                              + countPS(str));

    }

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

python3

# Python3 код для графа Палиндромика
# Подпоследовательность в данной строке

  
# Функция возвращает сумму
# палиндромная подпоследовательность

def countPS(str):

  

    N = len(str)

      

    # Создать 2D массив для хранения счетчика

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

    cps = [[0 for i in range(N + 2)]for j in range(N + 2)]

      

    # палиндромная подпоследовательность длины 1

    for i in range(N):

        cps[i][i] = 1

      

    # проверить подпоследовательность длины L

    # палиндром или нет

    for L in range(2, N + 1):

      

        for i in range(N):

            k = L + i - 1

            if (k < N):

                if (str[i] == str[k]):

                    cps[i][k] = (cps[i][k - 1] +

                                cps[i + 1][k] + 1)

                else:

                    cps[i][k] = (cps[i][k - 1] +

                                cps[i + 1][k] -

                                cps[i + 1][k - 1])

      

    # вернуть полную палиндромную подпоследовательность

    return cps[0][N - 1]

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

str = "abcb"

print("Total palindromic subsequence are : "

                            , countPS(str))

  

  
# Этот код предоставлен Anant Agarwal.

C #

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

using System;

  

class GFG {

      

    // Функция возвращает сумму

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

    static int countPS(string str)

    {

        int N = str.Length;

      

        // создаем 2D массив для хранения

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

        int[,] cps = new int[N + 1, N + 1];

      

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

        // длины 1

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

            cps[i, i] = 1;

      

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

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

        for (int L = 2; L <= N; L++)

        {

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

            {

                int k = L + i - 1;

                if (k < N) {

                if (str[i] == str[k])

                    cps[i, k] = cps[i, k - 1] + 

                                cps[i + 1, k] + 1;

                else

                    cps[i, k] = cps[i, k - 1] +

                                cps[i + 1, k] -

                                cps[i + 1, k - 1];

                }

            }

        }

      

        // возвращаем общее палиндромное

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

        return cps[0, N - 1];

    }

      

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

    public static void Main()

    {

        string str = "abcb";

        Console.Write("Total palindromic "+

                       "subsequence are : "

                           + countPS(str));

    }

}

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

PHP

<?php 
// Подсчитывает палиндромную подпоследовательность в
// данная строка

  
// Функция возвращает сумму
// палиндромная подпоследовательность

function countPS($str)

{

    $N = strlen($str);

  

    // создаем 2D массив для хранения

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

    $cps = array_fill(0, $N + 1, 

           array_fill(0, $N + 1, NULL));

  

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

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

        $cps[$i][$i] = 1;

  

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

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

    for ($L = 2; $L <= $N; $L++)

    {

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

        {

            $k = $L + $i - 1;

            if ($str[$i] == $str[$k])

                $cps[$i][$k] = $cps[$i][$k - 1] +

                               $cps[$i + 1][$k] + 1;

            else

                $cps[$i][$k] = $cps[$i][$k - 1] +

                               $cps[$i + 1][$k] -

                               $cps[$i + 1][$k - 1];

        }

    }

  

    // возвращаем полную палиндромную подпоследовательность

    return $cps[0][$N - 1];

}

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

$str = "abcb";

echo "Total palindromic subsequence are : " .

                        countPS($str) . "\n";

  
// Этот код предоставлен ita_c
?>


Выход:

Total palindromic subsequence are : 6

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

Другой подход: (с использованием рекурсии)

C ++

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

using namespace std;

  

int n,dp[1000][1000];

  

string str = "abcb"

  

 // Функция возвращает сумму

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

int countPS(int i,int j)

{

      

    if(i>=n||j<0)

    return 0;

      

    if(dp[i][j]!=-1)

    return dp[i][j];

      

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

    if(abs(i-j)==1)

    {

        if(str[i]==str[j]) // eg-> aaa

        return dp[i][j] = 3;

        else             // eg-> ab

        return dp[i][j] = 2;

    }

      

    if(i==j)

    return dp[1][j] = 1;

      

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

return dp[i][j] = countPS(i+1, j) + 

                    countPS(i, j-1) + 1;

      
else

return dp[i][j] = countPS(i+1, j) + 

                  countPS(i, j-1) - countPS(i+1, j-1);

      
}

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

int main()

{

    memset(dp,-1,sizeof(dp));

      

    n=str.size();

    cout << "Total palindromic subsequence are : "

        << countPS(0,n-1) << endl; 

          

    return 0; 

      
}
// этот код предоставлен Kushdeep Mittal

Джава

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

  

class GFG 

    static int n; 

    static int[][] dp = new int[1000][1000]; 

  

    static String str = "abcb"

      

    // Функция возвращает сумму

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

    static int countPS(int i, int j) 

    

          

        if(i >= n || j < 0

            return 0

          

        if(dp[i][j] != -1

            return dp[i][j]; 

          

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

        if((i - j == 1) || (i - j == -1)) 

        

            // eg-> aaa

            if(str.charAt(i) == str.charAt(j)) 

                return dp[i][j] = 3

            else             // eg-> ab

                return dp[i][j] = 2

        

          

        if(i == j) 

            return dp[1][j] = 1

          

        else if (str.charAt(i) == str.charAt(j)) 

            return dp[i][j] = countPS(i + 1, j) + 

                        countPS(i, j - 1) + 1

          

        else

        return dp[i][j] = countPS(i + 1, j) + 

                            countPS(i, j - 1) - 

                            countPS(i + 1, j - 1); 

          

    

      

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

    public static void main(String[] args) 

    

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

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

                dp[i][j] = -1

      

        n=str.length(); 

            System.out.println("Total palindromic subsequence"

                            "are : "+ countPS(0,n-1)); 

    

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

Python 3

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

  

str = "abcb"

  
# Функция возвращает сумму
# палиндромная подпоследовательность

def countPS(i, j):

      

    if(i >= n or j < 0):

        return 0

      

    if(dp[i][j] != -1):

        return dp[i][j]

      

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

    if(abs(i - j) == 1):

          

        if(str[i] == str[j]) : # eg-> aaa

            dp[i][j] = 3

            return dp[i][j]

        else :         # eg-> ab

            dp[i][j] = 2

            return dp[i][j]

      

    if(i == j):

        dp[1][j] = 1

        return dp[1][j]

      

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

        dp[i][j] = (countPS(i + 1, j) + 

                    countPS(i, j - 1) + 1)

        return dp[i][j]

    else:

        dp[i][j] = (countPS(i + 1, j) + 

                    countPS(i, j - 1) -

                    countPS(i + 1, j - 1))

        return dp[i][j]

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

if __name__ == "__main__":

      

    dp = [[-1 for x in range(1000)]

              for y in range(1000)]

      

    n = len(str)

    print("Total palindromic subsequence are :"

                              countPS(0, n - 1))

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

C #

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

using System; 

  

class GFG 

    static int n;

    static int[,] dp = new int[1000, 1000]; 

  

    static string str = "abcb"

      

    // Функция возвращает сумму

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

    static int countPS(int i, int j) 

    

          

        if(i >= n || j < 0) 

        return 0; 

          

        if(dp[i, j] != -1) 

        return dp[i, j]; 

          

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

        if((i - j == 1) || (i - j == -1)) 

        

            if(str[i] == str[j]) // eg-> aaa

            return dp[i, j] = 3; 

            else             // eg-> ab

            return dp[i, j] = 2; 

        

          

        if(i == j) 

        return dp[1, j] = 1; 

          

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

    return dp[i, j] = countPS(i + 1, j) + 

                      countPS(i, j - 1) + 1; 

          

    else

    return dp[i, j] = countPS(i + 1, j) + 

                      countPS(i, j - 1) - 

                      countPS(i + 1, j - 1); 

          

    

      

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

    static void Main() 

    

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

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

                dp[i, j] = -1;

      

        n=str.Length; 

        Console.Write("Total palindromic subsequence" +

                            "are : "+ countPS(0,n-1));

    }

}

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

PHP

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

$dp = array_fill(0, 100, 

      array_fill(0, 1000, -1));

  

$str = "abcb"

$n = strlen($str);

  
// Функция возвращает сумму
// палиндромная подпоследовательность

function countPS($i, $j)

{

    global $str, $dp, $n;

      

    if($i >= $n || $j < 0)

        return 0;

      

    if($dp[$i][$j] != -1)

        return $dp[$i][$j];

      

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

    if(abs($i-$j) == 1)

    {

        if($str[$i] == $str[$j]) // eg-> aaa

            return $dp[$i][$j] = 3;

        else             // eg-> ab

            return $dp[$i][$j] = 2;

    }

      

    if($i == $j)

        return $dp[1][$j] = 1;

      

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

        return $dp[$i][$j] = countPS($i + 1, $j) + 

                             countPS($i, $j - 1) + 1;

      

    else

        return $dp[$i][$j] = countPS($i + 1, $j) + 

                             countPS($i, $j - 1) - 

                             countPS($i + 1, $j - 1);

}

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

echo "Total palindromic subsequence are : "

                          countPS(0, $n - 1); 

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

Выход:

Total palindromic subsequence are : 6

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

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

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

Подсчитать всю палиндромную подпоследовательность в данной строке

0.00 (0%) 0 votes