Is Subsequence

Q: ¿Cuál es la complejidad temporal de Is Subsequence?

La solución de dos punteros se ejecuta en tiempo O(n + m) , donde n y m son las longitudes de s y t , y utiliza memoria adicional O(1) . En la práctica, el bucle se detiene después de como máximo m pasos. La tabla de prefijos requiere un tiempo O(n × m) .

Q: ¿Por qué funciona el enfoque voraz de dos punteros para Is Subsequence?

Emparejar una letra de s en su posición más temprana posible dentro de t deja la mayor parte posible de t para las letras restantes. Cualquier colocación que use una copia posterior puede cambiarse para usar la anterior sin alterar el orden, así que, si existe alguna colocación, el método voraz la encuentra.

Q: ¿Cómo compruebas rápidamente muchas cadenas con el mismo t?

Prepara t una vez: para cada letra, almacena la lista ordenada de índices en los que aparece. Para colocar s[i] , busca mediante búsqueda binaria en la lista de esa letra el primer índice posterior a la coincidencia anterior. Cada comprobación cuesta entonces O(n log m) en lugar de O(m) .

FácilDos punteros

+10

Recibes dos cadenas, s y t. Devuelve true si puedes convertir t en s eliminando algunas de sus letras (posiblemente ninguna) mientras las letras restantes mantienen su orden, y false en caso contrario. Por ejemplo, ace es una subsecuencia de abcde, pero aec no lo es.

Función

isSubsequence(s: string, t: string) → boolean

sstring: la cadena que se debe buscar
tstring: la cadena de la que se eliminarán letras
Devuelveboolean: verdadero si s se puede leer dentro de t en orden, posiblemente con espacios

Restricciones

1 ≤ s.length ≤ 3 × 10⁴
1 ≤ t.length ≤ 5 × 10⁴
s y t solo contienen letras minúsculas del inglés.

Ejemplos

Entrada: s = "ace"t = "abcde"
Salida: true
Explicación: Elimina b y d de abcde y queda ace, en el mismo orden.

Entrada: s = "aec"t = "abcde"
Salida: false
Explicación: t tiene las tres letras, pero la única c está antes de la única e. Después de usar la e en el índice 4, no queda ninguna c a su derecha.

Entrada: s = "moon"t = "monsoon"
Salida: true
Explicación: Usa la m en el índice 0, las o en los índices 1 y 4, y la n en el índice 6 de monsoon. Las letras que están entre ellas se eliminan.

+20 pruebas ocultas al enviar

Para ir más allá

Supón que t permanece igual y tienes que comprobar un millón de cadenas diferentes s comparándolas con él. ¿Cómo prepararías t para que cada comprobación sea más rápida que volver a leer todo t?

Pistas

Ábrelas de una en una. Cada una revela un poco más.

0 de 3 abiertas

Solución

Una subsecuencia puede saltarse letras de t en cualquier parte, así que puede parecer que tienes que probar muchas maneras de colocar s dentro de t. No es así. Hacer coincidir cada letra de s en el primer lugar donde pueda ir nunca es peor que cualquier otra opción, y eso convierte la búsqueda en un único recorrido de izquierda a derecha con dos punteros.

Programación dinámica sobre prefijos

Correcto, pero no termina con las pruebas más grandes

Intuición

Haz una pregunta más pequeña: ¿las primeras i letras de s caben en las primeras j letras de t? Llama dp[i][j] a la respuesta. Si caben en t[:j-1], también caben en t[:j], ya que puedes eliminar t[j-1]. Si s[i-1] es igual a t[j-1], también puedes usar esa letra, y entonces las primeras i-1 letras de s deben caber en t[:j-1]. Así que dp[i][j] = dp[i][j-1] or (s[i-1] == t[j-1] and dp[i-1][j-1]), y el prefijo vacío de s cabe en cualquier lugar.

La fila i solo lee la fila i-1, así que bastan dos filas de longitud m+1. La respuesta está en la última celda de la última fila.

Esta es la misma tabla que construyes para la subsecuencia común más larga, y es correcta, pero llena todas las celdas. Con s de 25 000 letras y t de 50 000, eso son 1.25 × 10^9 celdas, muchas más de las que necesita un solo recorrido de las dos cadenas.

Algoritmo

Crea una fila prev de m+1 valores, todos true: una s vacía encaja en cada prefijo de t.
Para cada i de 1 a n, crea una fila cur con cur[0] = false.
Para cada j de 1 a m, establece cur[j] en cur[j-1], o en prev[j-1] cuando s[i-1] sea igual a t[j-1].
Reemplaza prev por cur.
Devuelve prev[m].

def isSubsequence(s, t):
    n, m = len(s), len(t)
    # prev[j]: the first i-1 letters of s fit inside t[:j]. An empty s fits anywhere.
    prev = [True] * (m + 1)
    for i in range(1, n + 1):
        cur = [False] * (m + 1)
        for j in range(1, m + 1):
            cur[j] = cur[j - 1] or (s[i - 1] == t[j - 1] and prev[j - 1])
        prev = cur
    return prev[m]

Dos punteros con emparejamiento voraz

Intuición

Lee t de izquierda a derecha y mantén un puntero i a la siguiente letra de s que todavía necesitas. Cuando t[j] sea igual a s[i], úsala y avanza i. En cualquier caso, avanza j. Si i llega al final de s, cada letra encontró un lugar en el orden correcto.

¿Por qué es seguro tomar la primera coincidencia? Supongamos que una ubicación válida usa una copia posterior de s[i]. Si la cambias por la copia más temprana, mantienes el orden y dejas más de t a la derecha para el resto de s, así que la elección voraz nunca descarta una ubicación existente. Para moon en monsoon, el puntero toma la o del índice 1, salta n y s, toma la o del índice 4 y termina en la n del índice 6.

j visita cada letra de t una vez e i solo avanza, así que el bucle se ejecuta como máximo m veces. Dos índices son toda la memoria que necesita.

Algoritmo

Establece i = 0 para s y j = 0 para t.
Mientras ambos índices estén dentro de sus cadenas, compara s[i] con t[j].
Si son iguales, incrementa i.
Incrementa j en todos los casos.
Devuelve si i es igual a la longitud de s.

def isSubsequence(s, t):
    i = j = 0
    while i < len(s) and j < len(t):
        if s[i] == t[j]:
            i += 1
        j += 1
    return i == len(s)

Errores comunes y casos límite

El bucle de dos punteros es corto, y sus errores aparecen en los extremos.

Buscar cada letra de s en cualquier parte de t, en vez de hacerlo después de la coincidencia anterior. Eso acepta aec en abcde, donde se rompe el orden.
Usar dos veces la misma letra. noon no es una subsecuencia de moon: moon tiene una sola n, en el índice 3, y no puede ser a la vez la primera y la última letra de noon.
Devolver si j llegó al final de t. El bucle suele terminar ahí, independientemente de si se encontró s; solo i te lo indica.
Olvidar que s puede ser más larga que t. abc frente a ab debe devolver false, como hace el bucle siempre que se detenga cuando se agote t.
Leer s[i] después de que i haya llegado al final de s. En Python o Java, esa lectura genera un error, así que comprueba i antes de comparar.

Preguntas frecuentes4

¿Cuál es la complejidad temporal de Is Subsequence?

La solución de dos punteros se ejecuta en tiempo O(n + m), donde n y m son las longitudes de s y t, y utiliza memoria adicional O(1). En la práctica, el bucle se detiene después de como máximo m pasos. La tabla de prefijos requiere un tiempo O(n × m).

¿Por qué funciona el enfoque voraz de dos punteros para Is Subsequence?

Emparejar una letra de s en su posición más temprana posible dentro de t deja la mayor parte posible de t para las letras restantes. Cualquier colocación que use una copia posterior puede cambiarse para usar la anterior sin alterar el orden, así que, si existe alguna colocación, el método voraz la encuentra.

¿Cómo compruebas rápidamente muchas cadenas con el mismo t?

Prepara t una vez: para cada letra, almacena la lista ordenada de índices en los que aparece. Para colocar s[i], busca mediante búsqueda binaria en la lista de esa letra el primer índice posterior a la coincidencia anterior. Cada comprobación cuesta entonces O(n log m) en lugar de O(m).

¿Cuál es la diferencia entre una subsecuencia y una subcadena?

Una subcadena es un bloque de letras consecutivas, mientras que una subsecuencia puede omitir letras siempre que se mantenga el mismo orden. ace es una subsecuencia de abcde, pero no es una subcadena de esta. Toda subcadena es una subsecuencia, pero no al revés.

Python

def isSubsequence(s, t):
    # Escribe el código aquí

Casos de prueba

Caso 1

Caso 2

Caso 3

Entrada

s = "ace"
t = "abcde"

Esperado

true