Subcadena común más larga en Python
- Subcadena común más larga en Python
- Subcadena común más larga usando bucles en Python
- Utilice la recursividad para encontrar la subcadena común más larga
- Use la programación dinámica para encontrar la subcadena común más larga en Python
- Conclusión
String en Python almacena una secuencia de caracteres para realizar varias operaciones en ellos. Las subcadenas son parte de estas cadenas.
En este artículo, necesitamos encontrar la subcadena común más larga entre dos cadenas dadas y discutiremos varias soluciones para la misma.
Subcadena común más larga en Python
Una subcadena es una secuencia contigua de caracteres dentro de una cadena dada. Puede ser de cualquier longitud.
El problema principal es que se nos han proporcionado dos cadenas y necesitamos encontrar una subcadena que sea común entre las cadenas dadas y que debería ser la más larga entre todas las subcadenas comunes posibles.
Input: str1 = "HaveAAppleRegularly"
str2 = "HaveAnAnApple"
Output: "Apple"
En el ejemplo anterior, tenemos dos subcadenas comunes entre las cadenas dadas, "Have" y "Apple". Pero dado que la longitud de la subcadena "Apple" es la más larga entre el resto de las subcadenas; por lo tanto, se mostrará como nuestro resultado.
Este problema se puede resolver utilizando varios conceptos como la recursividad y la programación dinámica.
Subcadena común más larga usando bucles en Python
Los bucles se pueden usar para iterar a través de una cadena. Podemos iterar a través de la cadena aquí usando los bucles y encontrar nuestra subcadena común más larga entre las dos cadenas dadas.
Usaremos los bucles for y while en este enfoque. Los siguientes son los pasos que deben seguirse para encontrar la subcadena común más larga en Python.
-
Estaremos encontrando todas las subcadenas de la primera cadena.
-
Comprobaremos que la subcadena actual de la primera cadena también es una subcadena de la segunda cadena.
-
Si ambas subcadenas coinciden, almacenaremos sus longitudes en una determinada variable y seguiremos actualizando esta variable.
-
Por último, la variable que almacena la longitud de la subcadena contendrá nuestro resultado deseado y se imprimirá.
Ejemplo de código:
str1 = "PokemonGo"
str2 = "StopPokemonLetsGo"
result = 0
for i in range(len(str1)):
for j in range(len(str2)):
k = 0
while (
(i + k) < len(str1) and (j + k) < len(str2) and str1[i + k] == str2[j + k]
):
k = k + 1
result = max(result, k)
print("Length of the longest common substring is:", result)
Producción :
Length of the longest common substring is: 7
Todas las subcadenas de la cadena se pueden calcular en el tiempo O(n^2), mientras que verificar que si la subcadena actual coincide con una subcadena de la segunda cadena tomaría el tiempo O(m). La complejidad temporal para el enfoque anterior sería O(n^2 * m), donde n y m son longitudes de las dos cadenas dadas, respectivamente.
Sin embargo, como no hemos tomado ningún espacio adicional para lograr la solución, la complejidad del espacio para la solución anterior sería O(1).
Utilice la recursividad para encontrar la subcadena común más larga
La recursividad se refiere a una función que se llama a sí misma. Necesitamos un caso base y el diagrama de elección para el problema en cuestión en recursividad.
Seguiremos los pasos a continuación para encontrar la subcadena común más larga en Python.
-
En el problema dado de encontrar la subcadena común más larga, la entrada más pequeña posible puede ser una cadena de longitud
0. Por lo tanto, el caso base sería comprobar si alguna de las longitudes de las entradas es0, entonces la función debería devolver un0. -
Ahora, compararemos los últimos caracteres de ambas cadenas, luego surgen dos casos en los que ambos caracteres coincidirían o no coincidirían entre sí.
-
Si el último carácter de cada una de las cadenas dadas coincide, entonces deberíamos llamar recursivamente al resto de las cadenas. Por lo tanto, reducimos las longitudes de ambas cadenas en
1y le sumamos uno para contar la longitud de la cadena. -
Sin embargo, si los caracteres no coinciden, se realiza una llamada recursiva a la primera cadena decrementando su longitud en
1y luego a la segunda cadena para decrementar su longitud en1. -
Se toma para nuestro resultado la longitud, la máxima entre las dos llamadas.
Ejemplo de código:
def LCS(s1, s2, n, m):
if n == 0 or m == 0:
return 0
if s1[n - 1] == s2[m - 1]:
return 1 + lcs(s1, s2, n - 1, m - 1)
else:
return max(lcs(s1, s2, n, m - 1), lcs(s1, s2, n - 1, m))
s1 = "pokemonGo"
s2 = "watchPokemon"
n = len(s1)
m = len(s2)
res = lcs(s1, s2, n, m)
print("Length of the longest common substring is:", res)
Producción :
Length of the longest common substring is: 7
La complejidad temporal de la solución anterior sería O(3^(m+n)), y la complejidad espacial sería O(m+n).
Use la programación dinámica para encontrar la subcadena común más larga en Python
La idea básica de la programación dinámica es encontrar las longitudes de todas las subcadenas de ambas cadenas y almacenar sus respectivas longitudes en una tabla. Dado que se usa la recursividad, existe la posibilidad de obtener un error de desbordamiento de pila porque, para entradas grandes, la pila de recursividad seguirá aumentando.
Introducimos el concepto de programación dinámica en la que formamos una tabla y seguiremos almacenando los resultados para las respectivas subcadenas. El mismo algoritmo que usamos en la recursividad también se usa con algunos cambios.
Ahora, discutiremos los pasos para encontrar la subcadena común más larga en Python.
-
Primero, inicialice la primera columna y la primera fila de la tabla. Estas celdas se inicializarán con valor
0como hemos visto en la condición base en recursividad. -
Usamos bucles en lugar de llamadas recursivas para nuestra lógica.
-
Dentro de los bucles, si el último carácter de ambas cadenas coincide, aumentamos la longitud de la celda en
1. -
De lo contrario, almacenamos la longitud máxima hasta la fila y columna adyacentes en la celda en particular.
-
Por último, nuestro resultado se almacenará en la última posición de la tabla; por lo tanto, devolvemos
dp[m][n].
Ejemplo de código:
def LCS(X, Y, m, n):
dp = [[0 for x in range(m + 1)] for y in range(n + 1)]
for i in range(m + 1):
for j in range(n + 1):
if X[i - 1] == Y[j - 1]:
dp[i][j] = dp[i - 1][j - 1] + 1
else:
dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])
return dp[m][n]
s1 = "playbatball"
s2 = "batballwicket"
n = len(s1)
m = len(s2)
res = lcs(s1, s2, n, m)
print("Length of the longest common substring is:", res)
Producción :
Length of the longest common substring is: 7
Dado que solo hay dos bucles en nuestra solución, la complejidad temporal de la solución anterior sería O(m*n). Estamos usando espacio adicional formando una tabla para almacenar los resultados.
La complejidad espacial de la solución anterior sería O(m*n).
Conclusión
Hemos aprendido tres enfoques diferentes para encontrar la subcadena común más larga entre dos cadenas dadas. El primer enfoque, un enfoque ingenuo, utiliza tres bucles y encuentra todas las subcadenas de la cadena dada y controla la más larga entre todas las subcadenas.
El segundo enfoque usa recursividad, mientras que el tercer enfoque usa programación dinámica para encontrar la subcadena común más larga en Python. El tercer enfoque sería el más rápido entre todas las soluciones discutidas en este artículo para resolver el problema y debería preferirse.