Word Break

Q: ¿Word Break es un problema de programación dinámica o de grafos?

Ambas perspectivas funcionan. Como programación dinámica, canEnd[i] responde si se pueden separar las primeras i letras, a partir de prefijos más pequeños. Como grafo, cada índice es un nodo con una arista de i a j cuando las letras desde i hasta j forman una palabra, y preguntas si el nodo n es alcanzable desde el nodo 0. Una búsqueda en anchura con un conjunto de visitados hace el mismo trabajo que la tabla.

MedioProgramación dinámica Hashing

+10

Se te da una cadena s y una lista de palabras wordDict. Devuelve true si puedes dividir s en partes de modo que cada parte sea una palabra de wordDict, y false en caso contrario.

Las partes conservan su orden y, en conjunto, usan cada letra de s exactamente una vez. Puedes usar una palabra cualquier número de veces y no tienes que usar todas las palabras.

Función

wordBreak(s: string, wordDict: string-array) → boolean

sstring: la cadena que se va a dividir en palabras
wordDictstring-array: las palabras que puedes usar, tantas veces como quieras
Devuelveboolean: true si s puede dividirse en palabras del diccionario, false en caso contrario

Restricciones

1 ≤ s.length ≤ 300
1 ≤ wordDict.length ≤ 1000
1 ≤ wordDict[i].length ≤ 20
s y cada palabra contiene únicamente letras minúsculas del alfabeto inglés.
Las palabras de wordDict son todas diferentes.

Ejemplos

Entrada: s = "sunflowerseed"wordDict = ["sun", "flow", "flower", "seed"]
Salida: true
Explicación: Divídelo como sun, flower, seed. Tomar flow después de sun no lleva a ninguna parte, ya que ninguna palabra empieza con er, que es lo que queda, así que la primera palabra que encaja no siempre es la correcta.

Entrada: s = "bananaban"wordDict = ["ban", "ana"]
Salida: true
Explicación: ban + ana + ban cubre la cadena y usa ban dos veces, lo cual está permitido.

Entrada: s = "pineappletart"wordDict = ["pine", "apple", "pineapple", "tar"]
Salida: false
Explicación: La cadena empieza con pine + apple o con pineapple, y en ambos casos queda tart. La única palabra que encaja ahí es tar, lo que deja una t suelta, así que ningún corte funciona.

+21 pruebas ocultas al enviar

Para ir más allá

Devuelve la menor cantidad de palabras que puede usar un corte válido, o -1 si s no se puede cortar. ¿Qué cambia en la tabla y cambia el tiempo de ejecución?

Pistas

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

0 de 3 abiertas

Solución

La estrategia voraz falla en ambas direcciones: tomar primero la palabra más corta hace que sunflowerseed se divida en sun + flow, y tomar primero la más larga divide carpetal en carpet y deja al sin encajar. Así que tienes que probar las opciones, y una cadena puede dividirse de exponencialmente muchas maneras. La clave es que si el resto de la cadena puede dividirse depende solo de dónde empieza el resto, así que solo hay n + 1 preguntas distintas. A continuación, n es la longitud de s, m el número de palabras y L la longitud de la palabra más larga.

Prueba cada palabra en cada posición

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

Intuición

Lee s desde la izquierda. Sea cual sea la primera pieza, debe ser una palabra por la que empiece s. Prueba cada palabra de ese tipo y, para cada una, plantea la misma pregunta sobre las letras que quedan. Si alguna palabra lleva a una división completa, la respuesta es true. Si ninguna lo hace, es false. Cuando no queda nada, has dividido todas las letras, así que eso cuenta como éxito.

Esto prueba todas las primeras palabras posibles, luego todas las segundas palabras posibles y así sucesivamente, por lo que no puede pasar por alto una división válida, y cada true que devuelve corresponde a una división real.

Es lento porque comprueba las mismas partes restantes una y otra vez. Toma 299 copias de a seguidas de una b, con las palabras a, aa y así sucesivamente hasta llegar a diez a. Todas las maneras de dividir las a en bloques de como máximo diez llegan a la b y fallan allí, y hay más de 10^89 maneras. La recursión tiene que probarlas todas antes de poder responder false.

Algoritmo

Escribe una función auxiliar canSplit(start) que indique si las letras desde el índice start hasta el final se pueden dividir en palabras.
Si start es igual a la longitud de s, devuelve true.
Para cada palabra, comprueba si s la contiene empezando en el índice start.
Si es así y canSplit(start + length of the word) es true, devuelve true.
Si ninguna palabra sirve, devuelve false. La respuesta es canSplit(0).

def wordBreak(s, wordDict):
    def can_split(start):
        # Can s[start:] be cut into dictionary words?
        if start == len(s):
            return True  # nothing left to cut
        for word in wordDict:
            if s.startswith(word, start) and can_split(start + len(word)):
                return True
        return False

    return can_split(0)

Recursión con una memoria

Intuición

La respuesta para un resto depende únicamente de dónde empieza, y start solo toma n + 1 valores. En el ejemplo de las a, el resto que empieza en el índice 20 se alcanza después de dos bloques de diez, después de veinte a individuales y de muchísimas otras maneras, y la respuesta es false siempre. Guarda la respuesta de cada posición de inicio la primera vez que la calcules y recupérala después.

Una casilla de memorización necesita tres estados: todavía no calculado, true y false. Las respuestas false son las que importan. Un true termina toda la búsqueda de inmediato, así que el trabajo que repite la recursión simple ocurre enteramente en ramas que fallan.

Cada posición de inicio se calcula una vez y prueba todas las palabras, comparando hasta L letras, así que el tiempo es O(n × m × L): como máximo, 300 × 1000 × 20 = 6 × 10^6 comprobaciones de letras en este caso. La memoria y la pila de llamadas ocupan O(n) espacio, y las llamadas se anidan hasta 300 niveles.

Algoritmo

Crea una memo con un espacio por índice, cada uno marcado como no calculado.
En canSplit(start), devuelve true al final de la cadena y devuelve la respuesta guardada si el espacio para start contiene una.
De lo contrario, prueba cada palabra que empieza en start, como en la recursión simple, y detente en la primera cuyo resto se pueda dividir.
Guarda el resultado en el espacio, incluido false, y devuélvelo.
Devuelve canSplit(0).

def wordBreak(s, wordDict):
    memo = [None] * len(s)  # memo[start]: answer for s[start:], None until worked out

    def can_split(start):
        if start == len(s):
            return True
        if memo[start] is not None:
            return memo[start]
        result = False
        for word in wordDict:
            if s.startswith(word, start) and can_split(start + len(word)):
                result = True
                break
        memo[start] = result
        return result

    return can_split(0)

Análisis ascendente de prefijos con un conjunto hash

Intuición

Cambia el enfoque y trabaja con prefijos. Haz que canEnd[i] indique si las primeras i letras se pueden dividir en palabras. El prefijo vacío no necesita palabras, así que canEnd[0] es true. Las primeras end letras se pueden dividir exactamente cuando su último fragmento, las letras desde start hasta end, es una palabra y las letras anteriores se pueden dividir; es decir, canEnd[start] es true. Rellena la tabla de izquierda a derecha y cada canEnd[start] que necesites ya se conocerá.

En lugar de comparar las m palabras en cada posición, coloca las palabras en un conjunto hash y busca los posibles últimos fragmentos. Ninguna palabra tiene más de L letras, así que solo pueden coincidir los L fragmentos que terminan en end. En sunflowerseed, canEnd pasa a ser true en 0, en 3 (sun), en 7 (flow), en 9 (flower) y en 13 (seed después de la posición 9), así que la respuesta es true. La posición 7 no lleva a ninguna parte, porque ninguna palabra empieza con er, y a la tabla no le importa.

Hay n posiciones, cada una busca como máximo L fragmentos, y construir y aplicar hash a un fragmento cuesta hasta L pasos. Eso es O(n × L²), como máximo 300 × 20 × 20 = 1.2 × 10^5 pasos por letra, independientemente del tamaño del diccionario. Crear el conjunto implica leer cada palabra una vez, O(m × L), así que el total es O(m × L + n × L²). El conjunto contiene las palabras, O(m × L) letras, y la tabla tiene n + 1 indicadores. No hay recursión.

Algoritmo

Coloca cada palabra en un conjunto hash y anota la longitud L de la palabra más larga.
Crea canEnd con n + 1 elementos, todos false, y establece canEnd[0] en true.
Para cada end de 1 a n, prueba cada length de 1 a min(L, end).
Si canEnd[end-length] es true y la parte de esa longitud que termina en end está en el conjunto, establece canEnd[end] en true y deja de probar longitudes.
Devuelve canEnd[n].

def wordBreak(s, wordDict):
    words = set(wordDict)
    longest = max(len(word) for word in wordDict)
    n = len(s)
    # can_end[i]: the first i letters split into dictionary words
    can_end = [False] * (n + 1)
    can_end[0] = True  # the empty prefix needs no words
    for end in range(1, n + 1):
        # The last word is s[end-length:end], and no word is longer than longest.
        for length in range(1, min(longest, end) + 1):
            if can_end[end - length] and s[end - length:end] in words:
                can_end[end] = True
                break
    return can_end[n]

Errores comunes y casos límite

La mayoría de las respuestas incorrectas se deben a decidirse por un corte demasiado pronto o a una búsqueda que nunca recuerda sus fallos.

Cortar de forma codiciosa. Tomar primero la palabra más larga divide carpetal en carpet y deja al, aunque car + petal funciona. Tomar primero la más corta falla con sunflowerseed.
Comprobar solo que cada letra de s aparezca en alguna palabra. Con las palabras aaaa y aa, todas las piezas tienen una longitud par, así que aaaaaaa, de siete letras, no se puede dividir.
Guardar solo las respuestas true en la memoria caché. Un true termina la búsqueda de todos modos. El trabajo repetido está en las ramas false, así que una memoria caché que no las incluya sigue teniendo un crecimiento exponencial.
Crear una tabla a la que le falta una entrada. canEnd[i] se refiere a las primeras i letras, y tanto 0 como n son válidos, así que se necesitan n + 1 entradas.
Comparar más allá del final de s cuando una palabra es más larga que lo que queda, como la palabra abc frente a ab. Comprueba las longitudes antes de comparar las letras.
En Lua y R, las posiciones de las cadenas empiezan en 1: una pieza de longitud k que termina en la letra e empieza en la letra e-k+1.

Preguntas frecuentes4

¿Cuál es la complejidad temporal de Word Break?

La tabla ascendente con un conjunto hash se ejecuta en tiempo O(m × L + n × L²), donde n es la longitud de s, m el número de palabras y L la palabra más larga. Crear el conjunto lee cada palabra una vez, y cada una de las n posiciones busca como máximo L fragmentos de hasta L letras. Si comparas cada palabra en cada posición, en cambio, es O(n × m × L). La recursión simple sin memoización es exponencial.

¿Por qué falla un enfoque voraz para Word Break?

Una regla codiciosa se queda con una palabra y nunca la reconsidera. La estrategia de elegir primero la más larga divide carpetal en carpet y al, mientras que car + petal funciona. La estrategia de elegir primero la más corta divide sunflowerseed en sun + flow y se atasca con erseed. La programación dinámica conserva cada posición a la que puede llegar algún corte, así que nunca pierde la correcta.

¿Word Break es un problema de programación dinámica o de grafos?

Ambas perspectivas funcionan. Como programación dinámica, canEnd[i] responde si se pueden separar las primeras i letras, a partir de prefijos más pequeños. Como grafo, cada índice es un nodo con una arista de i a j cuando las letras desde i hasta j forman una palabra, y preguntas si el nodo n es alcanzable desde el nodo 0. Una búsqueda en anchura con un conjunto de visitados hace el mismo trabajo que la tabla.

¿Cómo enumeras cada oración en lugar de devolver verdadero o falso?

Usa retroceso: en cada índice, prueba todas las palabras que encajen y llama recursivamente con el resto, formando la oración a medida que avanzas. Recuerda la lista de oraciones para cada índice para resolver cada resto una sola vez. Ejecuta primero la tabla de verdadero o falso, para que una cadena que no se pueda dividir omita la búsqueda. La cantidad de oraciones puede crecer exponencialmente, así que el tamaño de la salida determina el tiempo de ejecución.

Python

def wordBreak(s, wordDict):
    # Escribe el código aquí

Casos de prueba

Caso 1

Caso 2

Caso 3

Entrada

s = "sunflowerseed"
wordDict = ["sun", "flow", "flower", "seed"]

Esperado

true

Word Break

Función

Restricciones

Ejemplos

Pistas

Solución

Prueba cada palabra en cada posición

Recursión con una memoria

Análisis ascendente de prefijos con un conjunto hash

Errores comunes y casos límite

Preguntas frecuentes4

Problemas similares