Menos borrados para igualar dos palabras
La misión
Problema
Dadas dos palabras a y b, un paso elimina un solo carácter de cualquiera de las dos. Devuelve la menor cantidad de pasos necesaria para que las dos palabras sean idénticas.
Ejemplos
Input: a = "sea", b = "eat"
Output: 2
Por qué: eliminas la s de sea y la t de eat, y queda ea en ambas
Input: a = "abcde", b = "ace"
Output: 2
Por qué: ace ya aparece dentro de abcde en orden, así que solo se van la b y la d
Input: a = "abc", b = ""
Output: 3
Por qué: caso límite: hay que eliminar todo lo de la primera palabra
Pistas
0 / 3
Lo que queda después de las eliminaciones aparece en ambas palabras, en el mismo orden. ¿Qué es lo máximo que podrías conservar?
Los caracteres que conservas forman una subsecuencia común de las dos palabras. Conservar la subsecuencia común más larga significa eliminar lo menos posible.
Calcula la longitud de la subsecuencia común más larga con una tabla donde la entrada (i, j) cubre los primeros i caracteres de a y los primeros j de b. La respuesta es len(a) + len(b) menos el doble de esa longitud.
- Tiempo objetivo
- O(m · n)
- Espacio objetivo
- O(m · n)
Solución
Eliminar caracteres hasta que las palabras coincidan deja un string (cadena) que es subsecuencia de ambas, así que el mínimo de eliminaciones sale de conservar la subsecuencia común más larga y quitar todo lo demás de cada palabra. La entrada de la tabla para los primeros i caracteres de a y los primeros j de b extiende en uno la entrada diagonal cuando los últimos caracteres coinciden y, si no, toma lo mejor entre descartar el último carácter de una u otra palabra. Cada carácter fuera de la subsecuencia común se elimina una vez, lo que da len(a) + len(b) - 2 * lcs. El tiempo es O(m · n) y el espacio es O(m · n) para palabras de longitudes m y n.
def min_deletions(a, b):
m, n = len(a), len(b)
lcs = [[0] * (n + 1) for _ in range(m + 1)]
for i in range(1, m + 1):
for j in range(1, n + 1):
if a[i - 1] == b[j - 1]:
lcs[i][j] = lcs[i - 1][j - 1] + 1 # keep the matching pair
else:
lcs[i][j] = max(lcs[i - 1][j], lcs[i][j - 1])
return m + n - 2 * lcs[m][n] # delete everything not kept
print(min_deletions("sea", "eat")) # -> 2
print(min_deletions("abcde", "ace")) # -> 2
print(min_deletions("abc", "")) # -> 3¿Lo que te frena es la idea y no el código? Subsecuencia común más larga lo explica.