[LeetCode] 1143. Subsecuencia común más larga

Explore diversas soluciones LeetCode en Python, C++, JavaScript, SQL y TypeScript. Ideal para preparación de entrevistas, aprendizaje y práctica de código en múltiples lenguajes de programación. Enlace de repositorio de Github

Tabla de contenido

Medio

Dadas dos cuerdas texto 1 y texto2, devolver la longitud de su más largo subsecuencia común. si no hay subsecuencia común, devolver 0.

A subsecuencia de una cadena es una nueva cadena generada a partir de la cadena original con algunos caracteres (puede ser ninguno) eliminados sin cambiar el orden relativo de los caracteres restantes.

Por ejemplo, "as" es una subsecuencia de "abcd".

A subsecuencia común de dos cadenas es una subsecuencia que es común a ambas cadenas.

Ejemplo 1:

Aporte: texto1 = "abcde", texto2 = "as" 
Producción: 3  
Explicación: La subsecuencia común más larga es "as" y su longitud es 3.

Ejemplo 2:

Aporte: texto1 = "abc", texto2 = "abc"
Producción: 3
Explicación: La subsecuencia común más larga es "abc" y su longitud es 3.

Ejemplo 3:

Aporte: texto1 = "abc", texto2 = "def"
Producción: 0
Explicación: No existe tal subsecuencia común, por lo que el resultado es 0.

Restricciones:

1 <= texto1.longitud, texto2.longitud <= 1000
texto 1 y texto2 constan únicamente de caracteres ingleses en minúscula.

Pitón

				
					Complejidad temporal de #: O(n*m) Complejidad espacial de #: clase O(n*m) Solución: def lowerCommonSubsequence(self, text1: str, text2: str) -> int: dpGrid = [[0] * (len( texto2) + 1) para _ en rango(len(text1)+1)] para col en invertido(rango(len(text2))): para fila en invertido(rango(len(text1))): si texto2[col ] == texto1[fila]: dpGrid[fila][col] = 1 + dpGrid[fila+1][col+1] más: dpGrid[fila][col] = max( dpGrid[fila+1][col] , dpGrid[fila][col+1]) return dpGrid[0][0] texto1 = "abcde" texto2 = "as" print(Solution().longestCommonSubsequence(texto1, texto2))

Medio

Pitón

Artículos relacionados