Dadas dos strings s1 y s2, la tarea es encontrar la longitud de la subsecuencia común más larga presente en ambas.
Ejemplos:
Entrada: s1 = “ABCDGH”, s2 = “AEDFHR”
Salida: 3
LCS para las Secuencias de entrada “AGGTAB” y “GXTXAYB” es “GTAB” de longitud 4.
Entrada: s1 = “striver”, s2 = “raj”
Salida: 1
La solución ingenua para este problema es generar todas las subsecuencias de ambas secuencias dadas y encontrar la subsecuencia coincidente más larga. Esta solución es exponencial en términos de complejidad temporal. La solución recursiva general del problema es generar todas las subsecuencias de ambas secuencias dadas y encontrar la subsecuencia coincidente más larga. El total de combinaciones posibles será 2 n . Por lo tanto, la solución recursiva tomará O(2 n ) .
Subestructura óptima:
- Deje que las secuencias de entrada sean X[0…m-1] e Y[0…n-1] de longitudes m y n respectivamente. Y sea L(X[0… m-1], Y[0…n-1]) la longitud de LCS de las dos secuencias X e Y. A continuación se muestra la definición recursiva de L(X[0… m-1 ], Y[0…n-1]).
- Si los últimos caracteres de ambas secuencias coinciden (o X[m-1] == Y[n-1]), entonces L(X[0…m-1], Y[0…n-1]) = 1 + L( X[0…m-2], Y[0…n-2])
- Si los últimos caracteres de ambas secuencias no coinciden (o X[m-1] != Y[n-1]) entonces L(X[0…m-1], Y[0…n-1]) = MAX ( L(X[0…m-2], Y[0…n-1]), L(X[0…m-1], Y[0…n-2])
A continuación se muestra la solución recursiva al problema LCS:
C++
// A Naive C++ recursive implementation
// of LCS of two strings
#include <bits/stdc++.h>
using namespace std;
// Returns length of LCS for X[0..m-1], Y[0..n-1]
int lcs(string X, string Y, int m, int n)
{
if (m == 0 || n == 0)
return 0;
if (X[m - 1] == Y[n - 1])
return 1 + lcs(X, Y, m - 1, n - 1);
else
return max(lcs(X, Y, m, n - 1),
lcs(X, Y, m - 1, n));
}
// Driver Code
int main()
{
string X = "AGGTAB";
string Y = "GXTXAYB";
// Find the length of string
int m = X.length();
int n = Y.length();
cout << "Length of LCS: " << lcs(X, Y, m, n);
return 0;
}
Java
// A Naive Java recursive implementation
// of LCS of two strings
class GFG {
// Returns length of LCS for X[0..m-1], Y[0..n-1]
static int lcs(String X, String Y, int m, int n) {
if (m == 0 || n == 0) {
return 0;
}
if (X.charAt(m - 1) == Y.charAt(n - 1)) {
return 1 + lcs(X, Y, m - 1, n - 1);
} else {
return Math.max(lcs(X, Y, m, n - 1),
lcs(X, Y, m - 1, n));
}
}
// Driver Code
public static void main(String[] args) {
String X = "AGGTAB";
String Y = "GXTXAYB";
// Find the length of String
int m = X.length();
int n = Y.length();
System.out.println("Length of LCS: " + lcs(X, Y, m, n));
}
}
// This code is contributed by 29AjayKumar
Python3
# A Naive Python recursive implementation
# of LCS of two strings
# Returns length of LCS for X[0..m-1], Y[0..n-1]
def lcs(X, Y, m, n):
if (m == 0 or n == 0):
return 0
if (X[m - 1] == Y[n - 1]):
return 1 + lcs(X, Y, m - 1, n - 1)
else:
return max(lcs(X, Y, m, n - 1),
lcs(X, Y, m - 1, n))
# Driver Code
if __name__ == '__main__':
X = "AGGTAB"
Y = "GXTXAYB"
# Find the length of string
m = len(X)
n = len(Y)
print("Length of LCS:",
lcs(X, Y, m, n))
# This code is contributed by 29AjayKumar
C#
// A Naive recursive C#implementation of
// LCS of two strings
using System;
class GFG
{
// Returns length of LCS for
// X[0..m-1], Y[0..n-1]
static int lcs(String X, String Y,
int m, int n)
{
if (m == 0 || n == 0)
{
return 0;
}
if (X[m - 1] == Y[n - 1])
{
return 1 + lcs(X, Y, m - 1, n - 1);
} else {
return Math.Max(lcs(X, Y, m, n - 1),
lcs(X, Y, m - 1, n));
}
}
// Driver Code
public static void Main()
{
String X = "AGGTAB";
String Y = "GXTXAYB";
// Find the length of String
int m = X.Length;
int n = Y.Length;
Console.Write("Length of LCS: " +
lcs(X, Y, m, n));
}
}
// This code is contributed by 29AjayKumar
PHP
<?php
// A Naive PHP recursive implementation
// of LCS of two strings
// Returns length of LCS for
// X[0..m-1], Y[0..n-1]
function lcs($X, $Y, $m, $n)
{
if ($m == 0 || $n == 0)
return 0;
if ($X[$m - 1] == $Y[$n - 1])
return 1 + lcs($X, $Y,
$m - 1, $n - 1);
else
return max(lcs($X, $Y, $m, $n - 1),
lcs($X, $Y, $m - 1, $n));
}
// Driver Code
$X = "AGGTAB";
$Y = "GXTXAYB";
// Find the length of string
$m = strlen($X);
$n = strlen($Y);
echo "Length of LCS: " . lcs($X, $Y, $m, $n);
// This code is contributed by ita_c
?>
Javascript
<script>
// A Naive Javascript recursive implementation
// of LCS of two strings
// Returns length of LCS for X[0..m-1], Y[0..n-1]
function lcs(X,Y,m,n)
{
if (m == 0 || n == 0) {
return 0;
}
if (X[m-1] == Y[n-1]) {
return 1 + lcs(X, Y, m - 1, n - 1);
} else {
return Math.max(lcs(X, Y, m, n - 1),
lcs(X, Y, m - 1, n));
}
}
// Driver Code
let X = "AGGTAB";
let Y = "GXTXAYB";
// Find the length of String
let m = X.length;
let n = Y.length;
document.write("Length of LCS: " + lcs(X, Y, m, n));
// This code is contributed by rag2127
</script>
Producción:
Length of LCS: 4
Programación Dinámica usando Memoización
Teniendo en cuenta la implementación anterior, el siguiente es un árbol de recurrencia parcial para las strings de entrada «AXYT» y «AYZX»
lcs("AXYT", "AYZX")
/ \
lcs("AXY", "AYZX") lcs("AXYT", "AYZ")
/ \ / \
lcs("AX", "AYZX") lcs("AXY", "AYZ") lcs("AXY", "AYZ") lcs("AXYT", "AY")
En el árbol de recursión parcial anterior, lcs(“AXY”, “AYZ”) se resuelven dos veces . Al dibujar el árbol de recursión completo, se ha observado que hay muchos subproblemas que se resuelven una y otra vez. Por lo tanto, este problema tiene la propiedad de subestructura superpuesta y el recálculo de los mismos subproblemas se puede evitar utilizando Memoization o Tabulation . El método de tabulación se ha discutido aquí.
Un punto común de observación para usar la memorización en el código recursivo serán los dos argumentos no constantes M y Nen cada llamada de función. La función tiene 4 argumentos, pero 2 argumentos son constantes, lo que no afecta la memorización. Las llamadas repetitivas ocurren para N y M que han sido llamados previamente. Seguir los pasos a continuación nos ayudará a escribir la solución DP utilizando la memorización.
- Use una array 2-D para almacenar el valor calculado de lcs(m, n) en arr[m-1][n-1] ya que el índice de string comienza desde 0.
- Siempre que se vuelva a llamar a la función con el mismo argumento m y n, no realice ninguna llamada recursiva adicional y devuelva arr[m-1][n-1] ya que el cálculo anterior de lcs(m, n) ya se ha almacenado en arr[m-1][n-1] , lo que reduce las llamadas recursivas que ocurren más de una vez.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program to memoize
// recursive implementation of LCS problem
#include <bits/stdc++.h>
using namespace std;
const int maximum = 1000;
// Returns length of LCS for X[0..m-1], Y[0..n-1] */
// memoization applied in recursive solution
int lcs(string X, string Y, int m, int n, int dp[][maximum])
{
// base case
if (m == 0 || n == 0)
return 0;
// if the same state has already been
// computed
if (dp[m - 1][n - 1] != -1)
return dp[m - 1][n - 1];
// if equal, then we store the value of the
// function call
if (X[m - 1] == Y[n - 1]) {
// store it in arr to avoid further repetitive
// work in future function calls
dp[m - 1][n - 1] = 1 + lcs(X, Y, m - 1, n - 1, dp);
return dp[m - 1][n - 1];
}
else {
// store it in arr to avoid further repetitive
// work in future function calls
dp[m - 1][n - 1] = max(lcs(X, Y, m, n - 1, dp),
lcs(X, Y, m - 1, n, dp));
return dp[m - 1][n - 1];
}
}
// Driver Code
int main()
{
string X = "AGGTAB";
string Y = "GXTXAYB";
int m = X.length();
int n = Y.length();
int dp[m][maximum];
// assign -1 to all positions
memset(dp, -1, sizeof(dp));
cout << "Length of LCS: " << lcs(X, Y, m, n, dp);
return 0;
}
Java
import java.util.Arrays;
// Java program to memoize
// recursive implementation of LCS problem
class GFG {
static final int maximum = 1000;
// Returns length of LCS for X[0..m-1], Y[0..n-1] */
// memoization applied in recursive solution
static int lcs(String X, String Y, int m, int n, int dp[][]) {
// base case
if (m == 0 || n == 0) {
return 0;
}
// if the same state has already been
// computed
if (dp[m - 1][n - 1] != -1) {
return dp[m - 1][n - 1];
}
// if equal, then we store the value of the
// function call
if (X.charAt(m - 1) == Y.charAt(n - 1)) {
// store it in arr to avoid further repetitive
// work in future function calls
dp[m - 1][n - 1] = 1 + lcs(X, Y, m - 1, n - 1, dp);
return dp[m - 1][n - 1];
} else {
// store it in arr to avoid further repetitive
// work in future function calls
dp[m - 1][n - 1] = Math.max(lcs(X, Y, m, n - 1, dp),
lcs(X, Y, m - 1, n, dp));
return dp[m - 1][n - 1];
}
}
// Driver Code
public static void main(String[] args) {
String X = "AGGTAB";
String Y = "GXTXAYB";
int m = X.length();
int n = Y.length();
int dp[][] = new int[m][maximum];
// assign -1 to all positions
for (int[] row : dp) {
Arrays.fill(row, -1);
}
System.out.println("Length of LCS: " + lcs(X, Y, m, n, dp));
}
}
/* This Java code is contributed by 29AjayKumar*/
Python3
# Python3 program to memoize
# recursive implementation of LCS problem
maximum = 1000
# Returns length of LCS for X[0..m-1], Y[0..n-1] */
# memoization applied in recursive solution
def lcs(X, Y, m, n, dp):
# base case
if (m == 0 or n == 0):
return 0
# if the same state has already been
# computed
if (dp[m - 1][n - 1] != -1):
return dp[m - 1][n - 1]
# if equal, then we store the value of the
# function call
if (X[m - 1] == Y[n - 1]):
# store it in arr to avoid further repetitive
# work in future function calls
dp[m - 1][n - 1] = 1 + lcs(X, Y, m - 1, n - 1, dp)
return dp[m - 1][n - 1]
else :
# store it in arr to avoid further repetitive
# work in future function calls
dp[m - 1][n - 1] = max(lcs(X, Y, m, n - 1, dp),
lcs(X, Y, m - 1, n, dp))
return dp[m - 1][n - 1]
# Driver Code
X = "AGGTAB"
Y = "GXTXAYB"
m = len(X)
n = len(Y)
dp = [[-1 for i in range(maximum)]
for i in range(m)]
print("Length of LCS:", lcs(X, Y, m, n, dp))
# This code is contributed by Mohit Kumar
C#
// C# program to memoize
// recursive implementation of LCS problem
using System;
class GFG
{
static readonly int maximum = 1000;
// Returns length of LCS for
// X[0..m-1], Y[0..n-1]
// memoization applied in
// recursive solution
static int lcs(String X, String Y,
int m, int n, int [,]dp)
{
// base case
if (m == 0 || n == 0)
{
return 0;
}
// if the same state has already been
// computed
if (dp[m - 1, n - 1] != -1)
{
return dp[m - 1, n - 1];
}
// if equal, then we store the value
// of the function call
if (X[m - 1] == Y[n - 1])
{
// store it in arr to avoid
// further repetitive work
// in future function calls
dp[m - 1,
n - 1] = 1 + lcs(X, Y, m - 1,
n - 1, dp);
return dp[m - 1, n - 1];
}
else
{
// store it in arr to avoid
// further repetitive work
// in future function calls
dp[m - 1,
n - 1] = Math.Max(lcs(X, Y, m, n - 1, dp),
lcs(X, Y, m - 1, n, dp));
return dp[m - 1, n - 1];
}
}
// Driver Code
public static void Main(String[] args)
{
String X = "AGGTAB";
String Y = "GXTXAYB";
int m = X.Length;
int n = Y.Length;
int [,]dp = new int[m, maximum];
// assign -1 to all positions
for(int i = 0; i < m; i++)
{
for(int j = 0; j < maximum; j++)
{
dp[i, j] = -1;
}
}
Console.WriteLine("Length of LCS: " +
lcs(X, Y, m, n, dp));
}
}
// This code is contributed by PrinciRaj1992
Javascript
<script>
// Javascript program to memoize
// recursive implementation of LCS problem
let maximum = 1000;
// Returns length of LCS for X[0..m-1], Y[0..n-1] */
// memoization applied in recursive solution
function lcs(X,Y,m,n,dp)
{
// base case
if (m == 0 || n == 0) {
return 0;
}
// if the same state has already been
// computed
if (dp[m - 1][n - 1] != -1) {
return dp[m - 1][n - 1];
}
// if equal, then we store the value of the
// function call
if (X[m-1] == Y[n-1]) {
// store it in arr to avoid further repetitive
// work in future function calls
dp[m - 1][n - 1] = 1 + lcs(X, Y, m - 1, n - 1, dp);
return dp[m - 1][n - 1];
} else {
// store it in arr to avoid further repetitive
// work in future function calls
dp[m - 1][n - 1] = Math.max(lcs(X, Y, m, n - 1, dp),
lcs(X, Y, m - 1, n, dp));
return dp[m - 1][n - 1];
}
}
// Driver Code
let X = "AGGTAB";
let Y = "GXTXAYB";
let m = X.length;
let n = Y.length;
let dp=new Array(m);
for(let i=0;i<dp.length;i++)
{
dp[i]=new Array(maximum);
for(let j=0;j<dp[i].length;j++)
{
dp[i][j]=-1;
}
}
document.write("Length of LCS: " + lcs(X, Y, m, n, dp));
// This code is contributed by avanitrachhadiya2155
</script>
Producción:
Length of LCS: 4
Complejidad de tiempo: O(N * M), donde N y M son longitudes de la primera y segunda string respectivamente.
Espacio Auxiliar: (N*M)