Dadas dos strings S y T, encuentre la longitud de la subsecuencia más corta en S que no sea una subsecuencia en T. Si no es posible tal subsecuencia, devuelva -1. Una subsecuencia es una secuencia que aparece en el mismo orden relativo, pero no necesariamente contigua. Una string de longitud n tiene 2^n posibles subsecuencias diferentes.
String S de longitud m (1 <= m <= 1000)
String T de longitud n (1 <= n <= 1000)
Ejemplos:
Input : S = “babab” T = “babba” Output : 3 The subsequence “aab” of length 3 is present in S but not in T. Input : S = “abb” T = “abab” Output : -1 There is no subsequence that is present in S but not in T.
Método de fuerza bruta
Un enfoque simple será generar todas las subsecuencias de la string S y para cada subsecuencia verificar si está presente en la string T o no. Considere el ejemplo 2 en el que S = “abb”,
sus subsecuencias son “”, ”a”, ”b”, ”ab”, ”bb”, ”abb”, cada una de las cuales está presente en “abab”. La complejidad temporal de esta solución será exponencial.
Eficiente (Programación Dinámica):
1. Subestructura óptima:
Considere dos strings S y T de longitud m y n respectivamente y deje que la función para encontrar la subsecuencia poco común más corta sea shortestSeq (char *S, char *T). Para cada carácter en S, si no está presente en T, entonces ese carácter es la respuesta en sí.
De lo contrario, si se encuentra en el índice k, tenemos la opción de incluirlo en la subsecuencia poco común más corta o no.
If it is included answer = 1 + ShortestSeq( S + 1, T + k + 1) If not included answer = ShortestSeq( S + 1, T) The minimum of the two is the answer.
Por lo tanto, podemos ver que este problema tiene una propiedad de subestructura óptima, ya que puede resolverse mediante el uso de soluciones a los subproblemas.
2. Subproblemas superpuestos:
A continuación se muestra una implementación recursiva simple del problema anterior.
C++
// A simple recursive C++ program to find shortest
// uncommon subsequence.
#include<bits/stdc++.h>
using namespace std;
#define MAX 1005
/* A recursive function to find the length of
shortest uncommon subsequence*/
int shortestSeq(char *S, char *T, int m, int n)
{
// S string is empty
if (m == 0)
return MAX;
// T string is empty
if (n <= 0)
return 1;
// Loop to search for current character
int k;
for (k=0; k < n; k++)
if (T[k] == S[0])
break;
// char not found in T
if (k == n)
return 1;
// Return minimum of following two
// Not including current char in answer
// Including current char
return min(shortestSeq(S+1, T, m-1, n),
1 + shortestSeq(S+1, T+k+1, m-1, n-k-1));
}
// Driver program to test the above function
int main()
{
char S[] = "babab";
char T[] = "babba";
int m = strlen(S), n = strlen(T);
int ans = shortestSeq(S, T, m, n);
if (ans >= MAX)
ans = -1;
cout << "Length of shortest subsequence is: "
<< ans << endl;
return 0;
}
Java
// A simple recursive Java program to find shortest
// uncommon subsequence.
import java.util.*;
class GFG
{
static final int MAX = 1005;
/* A recursive function to find the length of
shortest uncommon subsequence*/
static int shortestSeq(char []S, char []T, int m, int n)
{
// S String is empty
if (m == 0)
return MAX;
// T String is empty
if (n <= 0)
return 1;
// Loop to search for current character
int k;
for (k = 0; k < n; k++)
if (T[k] == S[0])
break;
// char not found in T
if (k == n)
return 1;
// Return minimum of following two
// Not including current char in answer
// Including current char
return Math.min(shortestSeq(Arrays.copyOfRange(S, 1, S.length), T, m - 1, n),
1 + shortestSeq(Arrays.copyOfRange(S, 1, S.length),
Arrays.copyOfRange(T, k + 1, T.length), m - 1, n - k - 1));
}
// Driver code
public static void main(String[] args)
{
char S[] = "babab".toCharArray();
char T[] = "babba".toCharArray();
int m = S.length, n = T.length;
int ans = shortestSeq(S, T, m, n);
if (ans >= MAX)
ans = -1;
System.out.print("Length of shortest subsequence is: "
+ ans +"\n");
}
}
// This code is contributed by Rajput-Ji
Python3
# A simple recursive Python
# program to find shortest
# uncommon subsequence.
MAX = 1005
# A recursive function to
# find the length of shortest
# uncommon subsequence
def shortestSeq(S, T, m, n):
# S String is empty
if m == 0:
return MAX
# T String is empty
if(n <= 0):
return 1
# Loop to search for
# current character
for k in range(n):
if(T[k] == S[0]):
break
# char not found in T
if(k == n):
return 1
# Return minimum of following
# two Not including current
# char in answer Including
# current char
return min(shortestSeq(S[1 : ], T, m - 1, n),
1 + shortestSeq((S[1 : ]), T[k + 1 : ],
m - 1, n - k - 1))
# Driver code
S = "babab"
T = "babba"
m = len(S)
n = len(T)
ans = shortestSeq(S, T, m, n)
if(ans >= MAX):
ans =- 1
print("Length of shortest subsequence is:", ans)
# This code is contributed by avanitrachhadiya2155
C#
// A simple recursive C# program to find shortest
// uncommon subsequence.
using System;
class GFG
{
static readonly int MAX = 1005;
/* A recursive function to find the length of
shortest uncommon subsequence*/
static int shortestSeq(char []S, char []T, int m, int n)
{
// S String is empty
if (m == 0)
return MAX;
// T String is empty
if (n <= 0)
return 1;
// Loop to search for current character
int k;
for (k = 0; k < n; k++)
if (T[k] == S[0])
break;
// char not found in T
if (k == n)
return 1;
// Return minimum of following two
// Not including current char in answer
// Including current char
char []St1 = new Char[S.Length - 1];
Array.Copy(S, 1, St1, 0, S.Length - 1);
char []St2 = new Char[S.Length - 1];
Array.Copy(S, 1, St2, 0, S.Length - 1);
char []Tt1 = new Char[T.Length - (k + 1)];
Array.Copy(T, k + 1, Tt1, 0, T.Length - (k + 1));
return Math.Min(shortestSeq(St1, T, m - 1, n),
1 + shortestSeq(St2, Tt1, m - 1, n - k - 1));
}
// Driver code
public static void Main(String[] args)
{
char []S = "babab".ToCharArray();
char []T = "babba".ToCharArray();
int m = S.Length, n = T.Length;
int ans = shortestSeq(S, T, m, n);
if (ans >= MAX)
ans = -1;
Console.Write("Length of shortest subsequence is: "
+ ans +"\n");
}
}
// This code is contributed by Rajput-Ji
Javascript
<script>
// JavaScript code to implement the approach
const MAX = 1005
// A recursive function to
// find the length of shortest
// uncommon subsequence
function shortestSeq(S, T, m, n){
// S String is empty
if(m == 0)
return MAX
// T String is empty
if(n <= 0)
return 1
let k;
// Loop to search for
// current character
for(k=0;k<n;k++){
if(T[k] == S[0])
break
}
// char not found in T
if(k == n)
return 1
// Return minimum of following
// two Not including current
// char in answer Including
// current char
return Math.min(shortestSeq(S.substring(1,), T, m - 1, n),
1 + shortestSeq((S.substring(1,)), T.substring(k + 1,),
m - 1, n - k - 1))
}
// Driver code
let S = "babab"
let T = "babba"
let m = S.length
let n = T.length
let ans = shortestSeq(S, T, m, n)
if(ans >= MAX)
ans =- 1
document.write("Length of shortest subsequence is: "+ ans,"</br>")
// This code is contributed by shinjanpatra
</script>
Producción
Length of shortest subsequence is: 3
Si dibujamos el árbol de recursión completo, podemos ver 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 Memoización o Tabulación. La siguiente es una implementación tabulada del problema.
C++
// A dynamic programming based C++ program
// to find shortest uncommon subsequence.
#include<bits/stdc++.h>
using namespace std;
#define MAX 1005
// Returns length of shortest common subsequence
int shortestSeq(char *S, char *T)
{
int m = strlen(S), n = strlen(T);
// declaring 2D array of m + 1 rows and
// n + 1 columns dynamically
int dp[m+1][n+1];
// T string is empty
for (int i = 0; i <= m; i++)
dp[i][0] = 1;
// S string is empty
for (int i = 0; i <= n; i++)
dp[0][i] = MAX;
for (int i = 1; i <= m; i++)
{
for (int j = 1; j <= n; j++)
{
char ch = S[i-1];
int k;
for (k = j-1; k >= 0; k--)
if (T[k] == ch)
break;
// char not present in T
if (k == -1)
dp[i][j] = 1;
else
dp[i][j] = min(dp[i-1][j], dp[i-1][k] + 1);
}
}
int ans = dp[m][n];
if (ans >= MAX)
ans = -1;
return ans;
}
// Driver program to test the above function
int main()
{
char S[] = "babab";
char T[] = "babba";
int m = strlen(S), n = strlen(T);
cout << "Length of shortest subsequence is : "
<< shortestSeq(S, T) << endl;
}
Java
// A dynamic programming based Java program
// to find shortest uncommon subsequence.
class GFG
{
static final int MAX = 1005;
// Returns length of shortest common subsequence
static int shortestSeq(char[] S, char[] T)
{
int m = S.length, n = T.length;
// declaring 2D array of m + 1 rows and
// n + 1 columns dynamically
int dp[][] = new int[m + 1][n + 1];
// T string is empty
for (int i = 0; i <= m; i++)
{
dp[i][0] = 1;
}
// S string is empty
for (int i = 0; i <= n; i++)
{
dp[0][i] = MAX;
}
for (int i = 1; i <= m; i++)
{
for (int j = 1; j <= n; j++)
{
char ch = S[i - 1];
int k;
for (k = j - 1; k >= 0; k--)
{
if (T[k] == ch)
{
break;
}
}
// char not present in T
if (k == -1)
{
dp[i][j] = 1;
}
else
{
dp[i][j] = Math.min(dp[i - 1][j],
dp[i - 1][k] + 1);
}
}
}
int ans = dp[m][n];
if (ans >= MAX)
{
ans = -1;
}
return ans;
}
// Driver code
public static void main(String[] args)
{
char S[] = "babab".toCharArray();
char T[] = "babba".toCharArray();
int m = S.length, n = T.length;
System.out.println("Length of shortest" +
"subsequence is : " +
shortestSeq(S, T));
}
}
// This code is contributed by 29AjayKumar
Python3
# A dynamic programming based Python program
# to find shortest uncommon subsequence.
MAX = 1005
# Returns length of shortest common subsequence
def shortestSeq(S: list, T: list):
m = len(S)
n = len(T)
# declaring 2D array of m + 1 rows and
# n + 1 columns dynamically
dp = [[0 for i in range(n + 1)]
for j in range(m + 1)]
# T string is empty
for i in range(m + 1):
dp[i][0] = 1
# S string is empty
for i in range(n + 1):
dp[0][i] = MAX
for i in range(1, m + 1):
for j in range(1, n + 1):
ch = S[i - 1]
k = j - 1
while k >= 0:
if T[k] == ch:
break
k -= 1
# char not present in T
if k == -1:
dp[i][j] = 1
else:
dp[i][j] = min(dp[i - 1][j],
dp[i - 1][k] + 1)
ans = dp[m][n]
if ans >= MAX:
ans = -1
return ans
# Driver Code
if __name__ == "__main__":
S = "babab"
T = "babba"
print("Length of shortest subsequence is:",
shortestSeq(S, T))
# This code is contributed by
# sanjeev2552
C#
// A dynamic programming based C# program
// to find shortest uncommon subsequence.
using System;
class GFG
{
static readonly int MAX = 1005;
// Returns length of shortest common subsequence
static int shortestSeq(char[] S, char[] T)
{
int m = S.Length, n = T.Length;
// declaring 2D array of m + 1 rows and
// n + 1 columns dynamically
int [,]dp = new int[m + 1, n + 1];
// T string is empty
for (int i = 0; i <= m; i++)
{
dp[i, 0] = 1;
}
// S string is empty
for (int i = 0; i <= n; i++)
{
dp[0, i] = MAX;
}
for (int i = 1; i <= m; i++)
{
for (int j = 1; j <= n; j++)
{
char ch = S[i - 1];
int k;
for (k = j - 1; k >= 0; k--)
{
if (T[k] == ch)
{
break;
}
}
// char not present in T
if (k == -1)
{
dp[i, j] = 1;
}
else
{
dp[i, j] = Math.Min(dp[i - 1, j],
dp[i - 1, k] + 1);
}
}
}
int ans = dp[m, n];
if (ans >= MAX)
{
ans = -1;
}
return ans;
}
// Driver code
public static void Main(String[] args)
{
char []S = "babab".ToCharArray();
char []T = "babba".ToCharArray();
int m = S.Length, n = T.Length;
Console.WriteLine("Length of shortest" +
"subsequence is : " +
shortestSeq(S, T));
}
}
// This code contributed by Rajput-Ji
PHP
<?php
// A dynamic programming based PHP program
// to find shortest uncommon subsequence.
$GLOBALS['MAX'] = 1005;
// Returns length of shortest
// common subsequence
function shortestSeq($S, $T)
{
$m = strlen($S);
$n = strlen($T);
// declaring 2D array of m + 1 rows
// and n + 1 columns dynamically
$dp = array(array());
// T string is empty
for ($i = 0; $i <= $m; $i++)
$dp[$i][0] = 1;
// S string is empty
for ($i = 0; $i <= $n; $i++)
$dp[0][$i] = $GLOBALS['MAX'];
for ($i = 1; $i <= $m; $i++)
{
for ($j = 1; $j <= $n; $j++)
{
$ch = $S[$i - 1];
for ($k = $j - 1; $k >= 0; $k--)
if ($T[$k] == $ch)
break;
// char not present in T
if ($k == -1)
$dp[$i][$j] = 1;
else
$dp[$i][$j] = min($dp[$i - 1][$j],
$dp[$i - 1][$k] + 1);
}
}
$ans = $dp[$m][$n];
if ($ans >= $GLOBALS['MAX'])
$ans = -1;
return $ans;
}
// Driver Code
$S = "babab";
$T = "babba";
$m = strlen($S);
$n = strlen($T);
echo "Length of shortest subsequence is : ",
shortestSeq($S, $T);
// This code is contributed by Ryuga
?>
Javascript
<script>
// A dynamic programming based JavaScript program
// to find shortest uncommon subsequence.
const MAX = 1005
// Returns length of shortest common subsequence
function shortestSeq(S, T)
{
let m = S.length, n = T.length;
// declaring 2D array of m + 1 rows and
// n + 1 columns dynamically
let dp = new Array(m+1).fill(0).map(()=>new Array(n+1).fill(0));
// T string is empty
for (let i = 0; i <= m; i++)
dp[i][0] = 1;
// S string is empty
for (let i = 0; i <= n; i++)
dp[0][i] = MAX;
for (let i = 1; i <= m; i++)
{
for (let j = 1; j <= n; j++)
{
let ch = S[i-1];
let k;
for (k = j-1; k >= 0; k--)
if (T[k] == ch)
break;
// char not present in T
if (k == -1)
dp[i][j] = 1;
else
dp[i][j] = Math.min(dp[i-1][j], dp[i-1][k] + 1);
}
}
let ans = dp[m][n];
if (ans >= MAX)
ans = -1;
return ans;
}
// Driver program to test the above function
let S = "babab";
let T = "babba";
let m = S.length, n = T.length;
document.write("Length of shortest subsequence is : "+shortestSeq(S, T),"</br>");
// This code is contributed by shinjanpatra
</script>
Producción
Length of shortest subsequence is : 3
Complejidad temporal: O(mn^2)
Complejidad espacial: O(mn)
Este artículo es una contribución de Aditi Sharma . 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.
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