Word Break

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

La tabla ascendente con un conjunto hash se ejecuta en 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. Comparar cada palabra en cada posición cuesta O(n × m × L) . La recursión simple es exponencial.

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

Ambos. En la programación dinámica, canEnd[i] indica si se pueden segmentar las primeras i letras. Como grafo, cada índice es un nodo, con una arista de i a j cuando las letras entre ellos forman una palabra, y preguntas si se puede llegar a n desde 0. Una búsqueda en anchura hace el mismo trabajo que la tabla.

MedioProgramación dinámica Hashing

+10

Recibes una cadena s y una lista de palabras wordDict. Devuelve true si puedes dividir s en partes que sean todas palabras de wordDict, y false en caso contrario.

Las partes mantienen su orden y, juntas, 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: verdadero si s se puede dividir en palabras del diccionario; falso en caso contrario

Restricciones

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

Ejemplos

Entrada: s = "sunflowerseed"wordDict = ["sun", "flow", "flower", "seed"]
Salida: true
Explicación: Córtalo como sun, flower, seed. Tomar flow después de sun deja er, con lo que ninguna palabra empieza, 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: Tanto pine + apple como pineapple dejan tart. Solo tar encaja ahí, lo que deja una t suelta, así que ningún corte funciona.

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

Comprometerse con una sola palabra a la vez no funciona, y probar cada corte tiene un coste exponencial. Pero que el resto de s se pueda dividir depende únicamente de dónde empieza, así que solo hay n + 1 preguntas. 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

La primera pieza debe ser una palabra por la que empiece s. Prueba cada una de esas palabras y haz la misma pregunta sobre las letras restantes; un resto vacío significa que se han cortado todas las letras. Probar todas las primeras palabras y después todas las segundas no puede pasar por alto ningún corte válido.

Comprueba los mismos restos una y otra vez. Con 299 copias de a seguidas de una b, y las palabras a, aa hasta diez as, más de 10^89 formas de dividir las a en bloques llegan hasta la b y fallan, y la recursión las prueba todas.

Algoritmo

Escribe canSplit(start): ¿se pueden dividir las letras desde start hasta el final? Si start es igual a la longitud de s, devuelve true.
Para cada palabra que s contiene en el índice start, si canSplit(start + its length) es true, devuelve true.
De lo contrario, 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 memoización

Intuición

La respuesta para un resto depende únicamente de start, que toma n + 1 valores. En el ejemplo con a, se llega al resto en el índice 20 después de dos bloques de diez, después de veinte a individuales y de innumerables otras maneras, y es false cada vez. Guarda una vez la respuesta de cada start y vuelve a usarla.

La memorización debe conservar las respuestas false. Un true termina toda la búsqueda de inmediato, así que todo el trabajo repetido está en las ramas que fallan.

Cada inicio prueba todas las palabras, comparando hasta L letras: tiempo O(n × m × L), como máximo 6 × 10^6 comprobaciones de letras y espacio O(n).

Algoritmo

Crea una tabla de memorización con una casilla por índice, cada una marcada como no resuelta.
En canSplit(start), devuelve true al final de s, o la respuesta almacenada si la casilla contiene una.
De lo contrario, prueba cada palabra como en la recursión simple, almacena el resultado en la casilla, incluido false, y devuélvelo.

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)

De abajo arriba sobre prefijos con un conjunto hash

Intuición

Trabaja con prefijos. Haz que canEnd[i] indique si las primeras i letras se pueden separar; canEnd[0] es true, ya que el prefijo vacío no necesita palabras. Las primeras end letras se pueden separar exactamente cuando la última pieza, desde start hasta end, es una palabra y canEnd[start] es true. Al rellenar de izquierda a derecha, ya se conoce cada canEnd[start] que necesitas.

Guarda las palabras en un conjunto hash. Ninguna palabra tiene más de L letras, así que solo pueden coincidir las L piezas que terminan en end, por grande que sea el diccionario. En sunflowerseed, canEnd es true en 0, 3, 7, 9 y 13; el callejón sin salida en 7 no causa ningún problema.

Cada una de las n posiciones busca como máximo L piezas, cada una con un coste de hasta L pasos para construirla y calcular su hash: O(n × L²), como máximo 1.2 × 10^5 pasos, más O(m × L) para el conjunto.

Algoritmo

Coloca las palabras en un conjunto hash; anota la longitud máxima L.
Crea canEnd con n + 1 elementos, todos false, y establece canEnd[0] en true.
Para cada end de 1 a n y 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 detente.
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

Cortar de forma codiciosa. Cortar primero las palabras más largas divide carpetal en carpet y deja colgado al, aunque car + petal funciona; cortar primero las más cortas se atasca con sunflowerseed.
Guardar en la memo solo las respuestas true. El trabajo repetido está en las ramas false, así que el ejemplo con a se mantiene exponencial.
Hacer que la tabla tenga una entrada menos. canEnd necesita n + 1 entradas, para longitudes de prefijo de 0 a n.
Comparar más allá del final de s, por ejemplo la palabra abc con el resto ab. Comprueba primero las longitudes.
En Lua y R, las posiciones de las cadenas empiezan en 1: una parte de longitud k que termina en la letra e empieza en e-k+1.

Preguntas frecuentes3

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

La tabla ascendente con un conjunto hash se ejecuta en 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. Comparar cada palabra en cada posición cuesta O(n × m × L). La recursión simple es exponencial.

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

Ambos. En la programación dinámica, canEnd[i] indica si se pueden segmentar las primeras i letras. Como grafo, cada índice es un nodo, con una arista de i a j cuando las letras entre ellos forman una palabra, y preguntas si se puede llegar a n desde 0. Una búsqueda en anchura hace el mismo trabajo que la tabla.

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

Retrocede: en cada índice, prueba todas las palabras que encajen, aplica la recursión al resto y recuerda la lista de oraciones para cada índice. Ejecuta primero la tabla de verdadero o falso para que una cadena que no se pueda dividir se salte la búsqueda. El número de oraciones puede crecer exponencialmente, así que el tamaño de la salida determina el tiempo de ejecución.

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

Prueba #1

Prueba #2

Prueba #3

Argumentos

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

Salida Esperada

true

Word Break

Función

Restricciones

Ejemplos

Pistas

Solución

Prueba cada palabra en cada posición

Recursión con memoización

De abajo arriba sobre prefijos con un conjunto hash

Errores comunes y casos límite

Preguntas frecuentes3

Problemas similares