Encuentre cuántas subsecuencias palindrómicas (no necesariamente deben ser distintas) se pueden formar en una string dada. Tenga en cuenta que la string vacía no se considera un palíndromo.
Ejemplos:
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
El problema anterior se puede definir recursivamente.
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)
Si dibujamos el árbol de recurrencia de la solución recursiva anterior, podemos observar subproblemas superpuestos . Dado que el problema tiene subproblemas superpuestos, podemos resolverlo de manera eficiente utilizando Programación Dinámica. A continuación se muestra una solución basada en programación dinámica.
Ejemplo
C++
// Counts Palindromic Subsequence in a given String
#include <cstring>
#include <iostream>
using namespace std;
// Function return the total palindromic subsequence
int countPS(string str)
{
int N = str.length();
// create a 2D array to store the count of palindromic
// subsequence
int cps[N + 1][N + 1];
memset(cps, 0, sizeof(cps));
// palindromic subsequence of length 1
for (int i = 0; i < N; i++)
cps[i][i] = 1;
// check subsequence of length L is palindrome or not
for (int L = 2; L <= N; L++) {
for (int i = 0; i <= N-L; 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 total palindromic subsequence
return cps[0][N - 1];
}
// Driver program
int main()
{
string str = "abcb";
cout << "Total palindromic subsequence are : "
<< countPS(str) << endl;
return 0;
}
Java
// Java code to Count Palindromic Subsequence
// in a given String
public class GFG {
// Function return the total palindromic
// subsequence
static int countPS(String str)
{
int N = str.length();
// create a 2D array to store the count
// of palindromic subsequence
int[][] cps = new int[N][N];
// palindromic subsequence of length 1
for (int i = 0; i < N; i++)
cps[i][i] = 1;
// check subsequence of length L is
// palindrome or not
for (int L = 2; L <= N; L++) {
for (int i = 0; i <= N-L; i++) {
int k = L + i - 1;
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 total palindromic subsequence
return cps[0][N - 1];
}
// Driver program
public static void main(String args[])
{
String str = "abcb";
System.out.println("Total palindromic "
+ "subsequence are : "
+ countPS(str));
}
}
// This code is contributed by Sumit Ghosh
Python3
# Python3 code to Count Palindromic
# Subsequence in a given String
# Function return the total
# palindromic subsequence
def countPS(str):
N = len(str)
# Create a 2D array to store the count
# of palindromic subsequence
cps = [[0 for i in range(N + 2)]for j in range(N + 2)]
# palindromic subsequence of length 1
for i in range(N):
cps[i][i] = 1
# check subsequence of length L
# is palindrome or not
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 total palindromic subsequence
return cps[0][N - 1]
# Driver program
str = "abcb"
print("Total palindromic subsequence are : ", countPS(str))
# This code is contributed by Anant Agarwal.
C#
// C# code to Count Palindromic Subsequence
// Subsequence in a given String
using System;
class GFG {
// Function return the total
// palindromic subsequence
static int countPS(string str)
{
int N = str.Length;
// create a 2D array to store the
// count of palindromic subsequence
int[, ] cps = new int[N + 1, N + 1];
// palindromic subsequence
// of length 1
for (int i = 0; i < N; i++)
cps[i, i] = 1;
// check subsequence of length
// L is palindrome or not
for (int L = 2; L <= N; L++) {
for (int i = 0; i <= N-L; 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 total palindromic
// subsequence
return cps[0, N - 1];
}
// Driver Code
public static void Main()
{
string str = "abcb";
Console.Write("Total palindromic "
+ "subsequence are : "
+ countPS(str));
}
}
// This code is contributed by nitin mittal.
PHP
<?php
// Counts Palindromic Subsequence in
// a given String
// Function return the total
// palindromic subsequence
function countPS($str)
{
$N = strlen($str);
// create a 2D array to store the
// count of palindromic subsequence
$cps = array_fill(0, $N + 1,
array_fill(0, $N + 1, NULL));
// palindromic subsequence of length 1
for ($i = 0; $i < $N; $i++)
$cps[$i][$i] = 1;
// check subsequence of length L
// is palindrome or not
for ($L = 2; $L <= $N; $L++)
{
for ($i = 0; $i <= $N-$L; $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 total palindromic subsequence
return $cps[0][$N - 1];
}
// Driver Code
$str = "abcb";
echo "Total palindromic subsequence are : " .
countPS($str) . "\n";
// This code is contributed by ita_c
?>
Javascript
<script>
// Javascript code to Count Palindromic Subsequence
// in a given String
// Function return the total palindromic
// subsequence
function countPS(str)
{
let N = str.length;
// create a 2D array to store the count
// of palindromic subsequence
let cps = new Array(N);
for(let i=0;i<N;i++)
{
cps[i]=new Array(N);
for(let j=0;j<N;j++)
{
cps[i][j]=0;
}
}
// palindromic subsequence of length 1
for (let i = 0; i < N; i++)
cps[i][i] = 1;
// check subsequence of length L is
// palindrome or not
for (let L = 2; L <= N; L++) {
for (let i = 0; i <= N-L; i++) {
let 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 total palindromic subsequence
return cps[0][N - 1];
}
// Driver program
let str = "abcb";
document.write("Total palindromic "
+ "subsequence are : "
+ countPS(str));
// This code is contributed by avanitrachhadiya2155
</script>
Producción:
Total palindromic subsequence are : 6
Complejidad de Tiempo: O(N 2 ), Espacio Auxiliar: O(N 2 )
Otro enfoque: (usando la recursividad)
C++
// C++ program to counts Palindromic Subsequence
// in a given String using recursion
#include <bits/stdc++.h>
using namespace std;
int n, dp[1000][1000];
string str = "abcb";
// Function return the total
// palindromic subsequence
int countPS(int i, int j)
{
if (i > j)
return 0;
if (dp[i][j] != -1)
return dp[i][j];
if (i == j)
return dp[i][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);
}
// Driver code
int main()
{
memset(dp, -1, sizeof(dp));
n = str.size();
cout << "Total palindromic subsequence are : "
<< countPS(0, n - 1) << endl;
return 0;
}
// this code is contributed by Kushdeep Mittal
Java
// Java program to counts Palindromic Subsequence
// in a given String using recursion
class GFG {
static int n;
static int[][] dp = new int[1000][1000];
static String str = "abcb";
// Function return the total
// palindromic subsequence
static int countPS(int i, int j)
{
if (i > j)
return 0;
if (dp[i][j] != -1)
return dp[i][j];
if (i == j)
return dp[i][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);
}
// Driver code
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));
}
}
// This code is contributed by Ryuga
Python 3
# Python 3 program to counts Palindromic
# Subsequence in a given String using recursion
str = "abcb"
# Function return the total
# palindromic subsequence
def countPS(i, j):
if(i > j):
return 0
if(dp[i][j] != -1):
return dp[i][j]
if(i == j):
dp[i][j] = 1
return dp[i][j]
else if (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]
# Driver code
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))
# This code is contributed by ita_c
C#
// C# program to counts Palindromic Subsequence
// in a given String using recursion
using System;
class GFG {
static int n;
static int[, ] dp = new int[1000, 1000];
static string str = "abcb";
// Function return the total
// palindromic subsequence
static int countPS(int i, int j)
{
if (i > j)
return 0;
if (dp[i, j] != -1)
return dp[i, j];
if (i == j)
return dp[i, 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);
}
// Driver code
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));
}
}
// This code is contributed by DrRoot_
PHP
<?php
// PHP program to counts Palindromic Subsequence
// in a given String using recursion
$dp = array_fill(0, 100,
array_fill(0, 1000, -1));
$str = "abcb";
$n = strlen($str);
// Function return the total
// palindromic subsequence
function countPS($i, $j)
{
global $str, $dp, $n;
if($i > $j)
return 0;
if($dp[$i][$j] != -1)
return $dp[$i][$j];
if($i == $j)
return $dp[$i][$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);
}
// Driver code
echo "Total palindromic subsequence are : " .
countPS(0, $n - 1);
// This code is contributed by mits
?>
Javascript
<script>
// Javascript program to counts Palindromic Subsequence
// in a given String using recursion
let n;
let dp=new Array(1000);
for(let i=0;i<1000;i++)
{
dp[i]=new Array(1000);
for(let j=0;j<1000;j++)
{
dp[i][j]=-1;
}
}
let str = "abcb";
// Function return the total
// palindromic subsequence
function countPS(i,j)
{
if (i > j)
return 0;
if (dp[i][j] != -1)
return dp[i][j];
if (i == j)
return dp[i][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);
}
// Driver code
n = str.length;
document.write("Total palindromic subsequence"
+ "are : " + countPS(0, n - 1));
// This code is contributed by rag2127
</script>
Producción:
Total palindromic subsequence are : 6
Complejidad de Tiempo: O(N 2 ), Espacio Auxiliar: O(N 2 )
Este artículo es una contribución de Aarti_Rathi y Nishant_sing. Si te gusta GeeksforGeeks y te gustaría contribuir, también puedes escribir un artículo usando write.geeksforgeeks.org o enviar tu artículo por correo a review-team@geeksforgeeks.org. Vea su artículo que aparece en la página principal de GeeksforGeeks y ayude a otros Geeks.
Escriba comentarios si encuentra algo incorrecto o si desea compartir más información sobre el tema tratado anteriormente.
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA