Dadas dos strings S y T, encuentre el conteo de ocurrencias distintas de T en S como una subsecuencia.
Ejemplos:
Input: S = banana, T = ban Output: 3 Explanation: T appears in S as below three subsequences. [ban], [ba n], [b an] Input: S = geeksforgeeks, T = ge Output: 6 Explanation: T appears in S as below three subsequences. [ge], [ ge], [g e], [g e] [g e] and [ g e]
Enfoque: Cree una función recursiva tal que devuelva el recuento de subsecuencias de S que coincidan con T . Aquí m es la longitud de T y n es la longitud de S. Este problema se puede definir recursivamente como se muestra a continuación.
- Dado que la string T es una string vacía, devolver 1 como una string vacía puede ser la subsecuencia de todos.
- Dado que la string S es una string vacía, devolver 0 como ninguna string puede ser la subsecuencia de una string vacía.
- Si el último carácter de S y T no coincide, elimine el último carácter de S y vuelva a llamar a la función recursiva. Porque el último carácter de S no puede ser parte de la subsecuencia o eliminarlo y buscar otros caracteres.
- Si el último carácter de S coincide, entonces puede haber dos posibilidades, primero puede haber una subsecuencia donde el último carácter de S es parte de ella y segundo donde no es parte de la subsecuencia. Entonces el valor requerido será la suma de ambos. Llame a la función recursiva una vez con el último carácter de ambas strings eliminado y nuevamente con solo el último carácter de S eliminado.
Los rectángulos redondos azules representan estados aceptados o hay una subsecuencia y los rectángulos redondos rojos representan No se puede formar una subsecuencia.
Implementación del enfoque recursivo:
C++
/* C/C++ program to count number of times S appears
as a subsequence in T */
#include <bits/stdc++.h>
using namespace std;
int f(int i, int j, string s, string t)
{
if (j >= t.size()) {
return 1;
}
if (i >= s.size()) {
return 0;
}
if (s[i] == t[j]) {
return f(i + 1, j + 1, s, t) + f(i + 1, j, s, t);
}
return f(i + 1, j, s, t);
}
int findSubsequenceCount(string s, string t)
{
return f(0, 0, s, t);
}
// Driver code to check above method
int main()
{
string T = "ge";
string S = "geeksforgeeks";
cout << findSubsequenceCount(S, T) << endl;
return 0;
}
Java
// Java program to count number of times
// S appears as a subsequence in T
import java.io.*;
class GFG {
static int f(int i, int j, String s,
String t)
{
// base case
// if second string completed then we found the
// matching pattern
if (j >= t.length()) {
return 1;
}
// if first string is completed we can not find any
// matching pattern.
if (i >= s.length()) {
return 0;
}
// if character at i'th place is equal to character
// at j'th place then
// we can either take it or not take it.
if (s.charAt(i) == t.charAt(j)) {
return f(i + 1, j + 1, s, t)
+ f(i + 1, j, s, t);
}
// if characters are not equal then we will increase
// only first string
return f(i + 1, j, s, t);
}
// Driver code to check above method
public static void main(String[] args)
{
String T = "ge";
String S = "geeksforgeeks";
System.out.println(
f(0, 0, S, T));
}
}
// This code is contributed by Sanskar.
C#
/* C# program to count number of times S appears
as a subsequence in T */
using System;
class GFG {
static int f(int i, int j, string s, string t)
{
if (j >= t.Length) {
return 1;
}
if (i >= s.Length) {
return 0;
}
if (s[i] == t[j]) {
return f(i + 1, j + 1, s, t) + f(i + 1, j, s, t);
}
return f(i + 1, j, s, t);
}
static int findSubsequenceCount(string s, string t)
{
return f(0, 0, s, t);
}
// Driver code to check above method
public static void Main()
{
string T = "ge";
string S = "geeksforgeeks";
Console.WriteLine(findSubsequenceCount(S, T));
}
}
// This code contributed by Pushpesh Raj.
Javascript
<script>
// Javascript program to count number of times S appears
// as a subsequence in T
function f(i, j, s, t) {
if (j >= t.length) {
return 1;
}
if (i >= s.length) {
return 0;
}
if (s[i] == t[j]) {
return f(i + 1, j + 1, s, t) + f(i + 1, j, s, t);
}
return f(i + 1, j, s, t);
}
function findSubsequenceCount(s, t) {
return f(0, 0, s, t);
}
// Driver code to check above method
let T = "ge";
let S = "geeksforgeeks";
document.write(findSubsequenceCount(S, T))
</script>
Producción
6
Dado que hay subproblemas superpuestos en el resultado de recurrencia anterior, se puede aplicar el enfoque de programación dinámica para resolver el problema anterior. Almacene los subproblemas en un Hashmap o una array y devuelva el valor cuando se vuelva a llamar a la función.
Algoritmo:
- Cree una array 2D mat[m+1][n+1] donde m es la longitud de la string T y n es la longitud de la string S. mat[i][j] denota el número de subsecuencias distintas de la substring S(1.. i) y la substring T(1..j) por lo que mat[m][n] contiene nuestra solución.
- Inicialice la primera columna con todos los 0. Una string vacía no puede tener otra string como subsecuencia
- Inicialice la primera fila con todos los 1. Una string vacía es una subsecuencia de todos.
- Rellene la array de forma ascendente, es decir, todos los subproblemas de la string actual se calculan primero.
- Recorre la cuerda T de principio a fin. (el contador es yo )
- Para cada iteración del bucle exterior, atraviesa la string S de principio a fin. (el contador es j )
- Si el carácter en el i -ésimo índice de la string T coincide con el j -ésimo carácter de la string S , el valor se obtiene considerando dos casos. Primero, son todas las substrings sin el último carácter en S y segundo son las substrings sin los últimos caracteres en ambos, es decir, mat[i+1][j] + mat[i][j] .
- De lo contrario, el valor será el mismo incluso si se elimina el j -ésimo carácter de S , es decir, mat[i+1][j]
- Imprime el valor de mat[m-1][n-1] como respuesta.
C++
/* C/C++ program to count number of times S appears
as a subsequence in T */
#include <bits/stdc++.h>
using namespace std;
int findSubsequenceCount(string S, string T)
{
int m = T.length(), n = S.length();
// T can't appear as a subsequence in S
if (m > n)
return 0;
// mat[i][j] stores the count of occurrences of
// T(1..i) in S(1..j).
int mat[m + 1][n + 1];
// Initializing first column with all 0s. An empty
// string can't have another string as subsequence
for (int i = 1; i <= m; i++)
mat[i][0] = 0;
// Initializing first row with all 1s. An empty
// string is subsequence of all.
for (int j = 0; j <= n; j++)
mat[0][j] = 1;
// Fill mat[][] in bottom up manner
for (int i = 1; i <= m; i++) {
for (int j = 1; j <= n; j++) {
// If last characters don't match, then value
// is same as the value without last character
// in S.
if (T[i - 1] != S[j - 1])
mat[i][j] = mat[i][j - 1];
// Else value is obtained considering two cases.
// a) All substrings without last character in S
// b) All substrings without last characters in
// both.
else
mat[i][j] = mat[i][j - 1] + mat[i - 1][j - 1];
}
}
/* uncomment this to print matrix mat
for (int i = 1; i <= m; i++, cout << endl)
for (int j = 1; j <= n; j++)
cout << mat[i][j] << " "; */
return mat[m][n];
}
// Driver code to check above method
int main()
{
string T = "ge";
string S = "geeksforgeeks";
cout << findSubsequenceCount(S, T) << endl;
return 0;
}
Java
// Java program to count number of times
// S appears as a subsequence in T
import java.io.*;
class GFG {
static int findSubsequenceCount(String S, String T)
{
int m = T.length();
int n = S.length();
// T can't appear as a subsequence in S
if (m > n)
return 0;
// mat[i][j] stores the count of
// occurrences of T(1..i) in S(1..j).
int mat[][] = new int[m + 1][n + 1];
// Initializing first column with
// all 0s. An emptystring can't have
// another string as subsequence
for (int i = 1; i <= m; i++)
mat[i][0] = 0;
// Initializing first row with all 1s.
// An empty string is subsequence of all.
for (int j = 0; j <= n; j++)
mat[0][j] = 1;
// Fill mat[][] in bottom up manner
for (int i = 1; i <= m; i++) {
for (int j = 1; j <= n; j++) {
// If last characters don't match,
// then value is same as the value
// without last character in S.
if (T.charAt(i - 1) != S.charAt(j - 1))
mat[i][j] = mat[i][j - 1];
// Else value is obtained considering two cases.
// a) All substrings without last character in S
// b) All substrings without last characters in
// both.
else
mat[i][j] = mat[i][j - 1] + mat[i - 1][j - 1];
}
}
/* uncomment this to print matrix mat
for (int i = 1; i <= m; i++, cout << endl)
for (int j = 1; j <= n; j++)
System.out.println ( mat[i][j] +" "); */
return mat[m][n];
}
// Driver code to check above method
public static void main(String[] args)
{
String T = "ge";
String S = "geeksforgeeks";
System.out.println(findSubsequenceCount(S, T));
}
}
// This code is contributed by vt_m
Python3
# Python3 program to count number of times # S appears as a subsequence in T def findSubsequenceCount(S, T): m = len(T) n = len(S) # T can't appear as a subsequence in S if m > n: return 0 # mat[i][j] stores the count of # occurrences of T(1..i) in S(1..j). mat = [[0 for _ in range(n + 1)] for __ in range(m + 1)] # Initializing first column with all 0s. x # An empty string can't have another # string as subsequence for i in range(1, m + 1): mat[i][0] = 0 # Initializing first row with all 1s. # An empty string is subsequence of all. for j in range(n + 1): mat[0][j] = 1 # Fill mat[][] in bottom up manner for i in range(1, m + 1): for j in range(1, n + 1): # If last characters don't match, # then value is same as the value # without last character in S. if T[i - 1] != S[j - 1]: mat[i][j] = mat[i][j - 1] # Else value is obtained considering two cases. # a) All substrings without last character in S # b) All substrings without last characters in # both. else: mat[i][j] = (mat[i][j - 1] + mat[i - 1][j - 1]) return mat[m][n] # Driver Code if __name__ == "__main__": T = "ge" S = "geeksforgeeks" print(findSubsequenceCount(S, T)) # This code is contributed # by vibhu4agarwal
C#
// C# program to count number of times
// S appears as a subsequence in T
using System;
class GFG {
static int findSubsequenceCount(string S, string T)
{
int m = T.Length;
int n = S.Length;
// T can't appear as a subsequence in S
if (m > n)
return 0;
// mat[i][j] stores the count of
// occurrences of T(1..i) in S(1..j).
int[, ] mat = new int[m + 1, n + 1];
// Initializing first column with
// all 0s. An emptystring can't have
// another string as subsequence
for (int i = 1; i <= m; i++)
mat[i, 0] = 0;
// Initializing first row with all 1s.
// An empty string is subsequence of all.
for (int j = 0; j <= n; j++)
mat[0, j] = 1;
// Fill mat[][] in bottom up manner
for (int i = 1; i <= m; i++) {
for (int j = 1; j <= n; j++) {
// If last characters don't match,
// then value is same as the value
// without last character in S.
if (T[i - 1] != S[j - 1])
mat[i, j] = mat[i, j - 1];
// Else value is obtained considering two cases.
// a) All substrings without last character in S
// b) All substrings without last characters in
// both.
else
mat[i, j] = mat[i, j - 1] + mat[i - 1, j - 1];
}
}
/* uncomment this to print matrix mat
for (int i = 1; i <= m; i++, cout << endl)
for (int j = 1; j <= n; j++)
System.out.println ( mat[i][j] +" "); */
return mat[m, n];
}
// Driver code to check above method
public static void Main()
{
string T = "ge";
string S = "geeksforgeeks";
Console.WriteLine(findSubsequenceCount(S, T));
}
}
// This code is contributed by vt_m
PHP
<?php
// PHP program to count number of times
// S appears as a subsequence in T */
function findSubsequenceCount($S, $T)
{
$m = strlen($T); $n = strlen($S);
// T can't appear as a subsequence in S
if ($m > $n)
return 0;
// mat[i][j] stores the count of
// occurrences of T(1..i) in S(1..j).
$mat = array(array());
// Initializing first column with all 0s.
// An empty string can't have another
// string as subsequence
for ($i = 1; $i <= $m; $i++)
$mat[$i][0] = 0;
// Initializing first row with all 1s.
// An empty string is subsequence of all.
for ($j = 0; $j <= $n; $j++)
$mat[0][$j] = 1;
// Fill mat[][] in bottom up manner
for ($i = 1; $i <= $m; $i++)
{
for ($j = 1; $j <= $n; $j++)
{
// If last characters don't match,
// then value is same as the value
// without last character in S.
if ($T[$i - 1] != $S[$j - 1])
$mat[$i][$j] = $mat[$i][$j - 1];
// Else value is obtained considering two cases.
// a) All substrings without last character in S
// b) All substrings without last characters in
// both.
else
$mat[$i][$j] = $mat[$i][$j - 1] +
$mat[$i - 1][$j - 1];
}
}
/* uncomment this to print matrix mat
for (int i = 1; i <= m; i++, cout << endl)
for (int j = 1; j <= n; j++)
cout << mat[i][j] << " "; */
return $mat[$m][$n];
}
// Driver Code
$T = "ge";
$S = "geeksforgeeks";
echo findSubsequenceCount($S, $T) . "\n";
// This code is contributed
// by Akanksha Rai
Javascript
<script>
// JavaScript program to count number of times
// S appears as a subsequence in T
function findSubsequenceCount(S, T)
{
let m = T.length;
let n = S.length;
// T can't appear as a subsequence in S
if (m > n)
return 0;
// mat[i][j] stores the count of
// occurrences of T(1..i) in S(1..j).
let mat = new Array(m + 1);
for (let i = 0; i <= m; i++)
{
mat[i] = new Array(n + 1);
for (let j = 0; j <= n; j++)
{
mat[i][j] = 0;
}
}
// Initializing first column with
// all 0s. An emptystring can't have
// another string as subsequence
for (let i = 1; i <= m; i++)
mat[i][0] = 0;
// Initializing first row with all 1s.
// An empty string is subsequence of all.
for (let j = 0; j <= n; j++)
mat[0][j] = 1;
// Fill mat[][] in bottom up manner
for (let i = 1; i <= m; i++) {
for (let j = 1; j <= n; j++) {
// If last characters don't match,
// then value is same as the value
// without last character in S.
if (T[i - 1] != S[j - 1])
mat[i][j] = mat[i][j - 1];
// Else value is obtained
// considering two cases.
// a) All substrings without
// last character in S
// b) All substrings without
// last characters in
// both.
else
mat[i][j] = mat[i][j - 1] +
mat[i - 1][j - 1];
}
}
/* uncomment this to print matrix mat
for (int i = 1; i <= m; i++, cout << endl)
for (int j = 1; j <= n; j++)
System.out.println ( mat[i][j] +" "); */
return mat[m][n];
}
let T = "ge";
let S = "geeksforgeeks";
document.write(findSubsequenceCount(S, T));
</script>
Producción
6
Análisis de Complejidad:
- Complejidad temporal: O(m*n).
Solo se necesita un recorrido de la array, por lo que la complejidad del tiempo es O (m * n) - Espacio Auxiliar: O(m*n).
Se necesita una array de tamaño m*n para que la complejidad del espacio sea O(m*n).
Nota: Dado que mat[i][j] accede a elementos de la fila actual y de la fila anterior únicamente, podemos optimizar el espacio auxiliar simplemente usando dos filas reduciendo el espacio de m*n a 2*n.
Otra forma de resolver la programación dinámica es mediante el enfoque de arriba hacia abajo mediante la memorización.
A continuación se muestra el código:
C++
/* C/C++ program to count number of times S appears
as a subsequence in T */
#include <bits/stdc++.h>
using namespace std;
int f(int i, int j, string s, string t,
vector<vector<int> >& dp)
{
if (t.size() - j > s.size() - i)
return 0;
if (j == t.size()) {
return 1;
}
if (i == s.size()) {
return 0;
}
if (dp[i][j] != -1) {
return dp[i][j];
}
if (s[i] == t[j]) {
return dp[i][j] = f(i + 1, j + 1, s, t, dp)
+ f(i + 1, j, s, t, dp);
}
return dp[i][j] = f(i + 1, j, s, t, dp);
}
int findSubsequenceCount(string s, string t)
{
vector<vector<int> > dp(s.size(),
vector<int>(t.size(), -1));
return f(0, 0, s, t, dp);
}
// Driver code to check above method
int main()
{
string T = "ge";
string S = "geeksforgeeks";
cout << findSubsequenceCount(S, T) << endl;
return 0;
}
Producción
6
Análisis de Complejidad:
- Complejidad temporal: O(m*n). Solo se necesita un recorrido de la array, por lo que la complejidad del tiempo es O (m * n)
- Espacio auxiliar: O(m*n) ignorando el espacio de la pila de recursividad
Este artículo es una contribución de Utkarsh Trivedi . 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