Word Break

Q: Word Break é um problema de programação dinâmica ou de grafos?

Ambos. Como programação dinâmica, canEnd[i] indica se as primeiras i letras podem ser separadas. Como grafo, cada índice é um nó, com uma aresta de i a j quando as letras entre eles formam uma palavra, e você verifica se n é alcançável a partir de 0. Uma busca em largura realiza o mesmo trabalho que a tabela.

MédioProgramação dinâmica Hashing

+10

Você recebe uma string s e uma lista de palavras wordDict. Retorne true se puder dividir s em partes que sejam todas palavras de wordDict, e false caso contrário.

As partes mantêm a ordem e, juntas, usam cada letra de s exatamente uma vez. Uma palavra pode ser usada qualquer número de vezes, e você não precisa usar todas as palavras.

Função

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

sstring: a string a ser dividida em palavras
wordDictstring-array: as palavras que você pode usar, quantas vezes quiser
Retornaboolean: verdadeiro se s puder ser dividido em palavras do dicionário; falso caso contrário

Restrições

1 ≤ s.length ≤ 300
1 ≤ wordDict.length ≤ 1000
1 ≤ wordDict[i].length ≤ 20
s e cada palavra contém apenas letras minúsculas do inglês.
As palavras em wordDict são todas diferentes.

Exemplos

Entrada: s = "sunflowerseed"wordDict = ["sun", "flow", "flower", "seed"]
Saída: true
Explicação: Divida como sun, flower, seed. Pegar flow depois de sun deixa er, com o qual nenhuma palavra começa, então a primeira palavra que se encaixa nem sempre é a correta.

Entrada: s = "bananaban"wordDict = ["ban", "ana"]
Saída: true
Explicação: ban + ana + ban cobre a string e usa ban duas vezes, o que é permitido.

Entrada: s = "pineappletart"wordDict = ["pine", "apple", "pineapple", "tar"]
Saída: false
Explicação: Tanto pine + apple quanto pineapple deixam tart. Só tar cabe ali, o que deixa um t sozinho, então nenhum corte funciona.

Para ir além

Retorne o menor número de palavras que um corte válido pode usar, ou -1 se s não puder ser cortada. O que muda na tabela e o tempo de execução muda?

Dicas

Abra uma de cada vez. Cada uma revela um pouco mais.

0 de 3 abertas

Solução

Comprometer-se com uma palavra de cada vez não funciona, e tentar todos os cortes tem custo exponencial. Mas a possibilidade de dividir o restante de s depende apenas de onde ele começa, então há apenas n + 1 perguntas. Abaixo, n é o comprimento de s, m o número de palavras e L o comprimento da palavra mais longa.

Tente cada palavra em cada posição

Correta, mas não termina nos maiores testes

Intuição

A primeira parte precisa ser uma palavra pela qual s começa. Tente cada palavra desse tipo e faça a mesma pergunta sobre as letras restantes; um restante vazio significa que todas as letras foram consumidas. Tentar cada primeira palavra e, em seguida, cada segunda palavra não pode deixar passar um corte válido.

Ele verifica os mesmos restos repetidamente. Com 299 cópias de a seguidas de um b, e as palavras a, aa até dez as, mais de 10^89 maneiras de dividir os a's em blocos chegam ao b e falham, e a recursão tenta todas elas.

Algoritmo

Escreva canSplit(start): as letras de start até o final podem ser separadas? Se start for igual ao comprimento de s, retorne true.
Para cada palavra que s contém no índice start, se canSplit(start + its length) for true, retorne true.
Caso contrário, retorne false. A resposta é 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)

Recursão com memoização

Intuição

A resposta para um restante depende apenas de start, que assume n + 1 valores. No exemplo com a's, o restante no índice 20 é alcançado após dois blocos de dez, após vinte as individuais e de inúmeras outras maneiras, e é false todas as vezes. Armazene a resposta de cada start uma vez e reutilize-a.

A memoização precisa manter as respostas false. Um true encerra toda a busca imediatamente, então todo o trabalho repetido acontece nos ramos que falham.

Cada start tenta todas as palavras, comparando até L letras: tempo O(n × m × L), no máximo 6 × 10^6 verificações de letras e espaço O(n).

Algoritmo

Crie uma tabela de memorização com uma posição para cada índice, cada uma marcada como ainda não calculada.
Em canSplit(start), retorne true no final de s ou a resposta armazenada, se houver uma na posição.
Caso contrário, tente cada palavra como na recursão simples, armazene o resultado na posição, incluindo false, e retorne-o.

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 baixo para cima, usando prefixos com um conjunto de hash

Intuição

Trabalhe com prefixos. Faça com que canEnd[i] indique se as primeiras i letras podem ser divididas; canEnd[0] é true, pois o prefixo vazio não precisa de palavras. As primeiras end letras podem ser divididas exatamente quando a última parte, de start a end, é uma palavra e canEnd[start] é true. Preenchidos da esquerda para a direita, todos os valores de canEnd[start] de que você precisa já são conhecidos.

Coloque as palavras em um conjunto hash. Nenhuma palavra tem mais que L letras, então somente as L partes que terminam em end podem corresponder, por maior que seja o dicionário. Em sunflowerseed, canEnd é true nas posições 0, 3, 7, 9 e 13; o beco sem saída na posição 7 não causa problema.

Cada uma das n posições consulta no máximo L partes, cada uma custando até L etapas para ser criada e passar pelo hash: O(n × L²), no máximo 1.2 × 10^5 etapas, mais O(m × L) para o conjunto.

Algoritmo

Coloque as palavras em um conjunto hash; observe o maior comprimento L.
Crie canEnd com n + 1 entradas, todas false, e defina canEnd[0] como true.
Para cada end de 1 a n e cada length de 1 a min(L, end): se canEnd[end-length] for true e o trecho desse comprimento que termina em end estiver no conjunto, defina canEnd[end] como true e pare.
Retorne 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]

Armadilhas e casos extremos

Fazer cortes de forma gulosa. Começar pela palavra mais longa divide carpetal em carpet e deixa al sem correspondência, embora car + petal funcione; começar pela mais curta fica preso em sunflowerseed.
Armazenar apenas as respostas true na memoização. O trabalho repetido está nos ramos false, então o exemplo com a's continua exponencial.
Fazer a tabela com uma entrada a menos. canEnd precisa de n + 1 entradas, para comprimentos de prefixo de 0 a n.
Comparar além do fim de s, como a palavra abc com o restante ab. Verifique os comprimentos primeiro.
Em Lua e R, as posições das strings começam em 1: um trecho de comprimento k que termina na letra e começa em e-k+1.

Perguntas frequentes3

Qual é a complexidade de tempo de Word Break?

A tabela de baixo para cima com um conjunto hash tem complexidade O(m × L + n × L²), em que n é o comprimento de s, m é o número de palavras e L é o comprimento da palavra mais longa. Comparar cada palavra em cada posição custa O(n × m × L). A recursão simples tem complexidade exponencial.

Word Break é um problema de programação dinâmica ou de grafos?

Ambos. Como programação dinâmica, canEnd[i] indica se as primeiras i letras podem ser separadas. Como grafo, cada índice é um nó, com uma aresta de i a j quando as letras entre eles formam uma palavra, e você verifica se n é alcançável a partir de 0. Uma busca em largura realiza o mesmo trabalho que a tabela.

Como listar cada frase em vez de retornar true ou false?

Use retrocesso: em cada índice, tente todas as palavras que se encaixam, faça uma chamada recursiva para o restante e guarde a lista de frases para cada índice. Primeiro, execute a tabela de verdadeiro ou falso, para que uma string que não possa ser dividida ignore a busca. O número de frases pode crescer exponencialmente, então o tamanho da saída determina o tempo de execução.

def wordBreak(s, wordDict):
    # Escreva o código aqui

Teste #1

Teste #2

Teste #3

Argumentos

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

Saída Esperada

true

Word Break

Função

Restrições

Exemplos

Dicas

Solução

Tente cada palavra em cada posição

Recursão com memoização

De baixo para cima, usando prefixos com um conjunto de hash

Armadilhas e casos extremos

Perguntas frequentes3

Problemas parecidos