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 , con memoria adicional O(1) . El bucle se detiene después de un máximo de m pasos. La tabla de prefijos requiere tiempo O(n × m) .

Q: ¿Qué relación tiene Is Subsequence con la subsecuencia común más larga?

s es una subsecuencia de t exactamente cuando su subsecuencia común más larga tiene longitud n , que es la longitud de s . La tabla de prefijos del primer enfoque es la que se construye para ese problema. Aquí solo necesitas saber si toda s encaja, así que basta con el recorrido voraz.

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 contienen solo 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 intermedias se eliminan.

Para ir más allá

Si t permanece fijo y comparas un millón de cadenas s con él, ¿cómo prepararías t para que cada comprobación sea más rápida que 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, lo que sugiere probar muchas ubicaciones de s. No hace falta: hacer coincidir cada letra de s en el primer lugar posible nunca es peor que cualquier otra opción, así que una pasada de izquierda a derecha con dos punteros lo determina.

Programación dinámica sobre prefijos

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

Intuición

Sea que dp[i][j] indique si las primeras i letras de s caben dentro de las primeras j letras de t. Caben si ya cabían sin t[j-1], o si s[i-1] es igual a t[j-1] y las primeras i-1 letras caben dentro de t[:j-1]. El prefijo vacío cabe en todas partes, y la fila i solo lee la fila i-1, así que bastan dos filas de longitud m+1.

La tabla llena todas las celdas: con s de 25,000 letras y t de 50,000, eso da 1.25 × 10^9 celdas.

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

Mantén un puntero i a la siguiente letra de s que necesitas y toma la primera copia que encuentres de ella en t. Esa elección es segura. Si una colocación válida usa una copia posterior de s[i], cambiarla por la copia más temprana conserva el orden y deja más de t para el resto de s. Así que, si existe alguna colocación, el método voraz la encuentra.

El bucle lee cada letra de t como máximo una vez y mantiene dos índices: tiempo O(n + m) y memoria O(1).

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

Buscar cada letra de s en cualquier parte de t, en lugar de hacerlo después de la coincidencia anterior. Eso acepta aec en abcde.
Usar dos veces la misma copia de una letra. noon no es una subsecuencia de moon: su única n, en el índice 3, no puede ser a la vez la primera y la última letra.
Devolver si j llegó al final de t. El bucle suele terminar ahí independientemente de si se encontró s; solo i te lo indica.
No detenerse cuando se agota t. La comparación de abc con ab debe devolver false.
Leer s[i] después de que i haya llegado al final de s. En Python o Java esa lectura provoca una excepción, así que comprueba i antes de comparar.

Preguntas frecuentes3

¿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, con memoria adicional O(1). El bucle se detiene después de un máximo de m pasos. La tabla de prefijos requiere tiempo O(n × m).

¿Qué relación tiene Is Subsequence con la subsecuencia común más larga?

s es una subsecuencia de t exactamente cuando su subsecuencia común más larga tiene longitud n, que es la longitud de s. La tabla de prefijos del primer enfoque es la que se construye para ese problema. Aquí solo necesitas saber si toda s encaja, así que basta con el recorrido voraz.

¿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 una subcadena. Toda subcadena es una subsecuencia, pero no al revés.

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

Prueba #1

Prueba #2

Prueba #3

Argumentos

s = "ace"
t = "abcde"

Salida Esperada

true