Word Break

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

As duas perspectivas funcionam. Na programação dinâmica, canEnd[i] indica se as primeiras i letras podem ser divididas, com base em prefixos menores. Como grafo, cada índice é um nó, com uma aresta de i a j quando as letras de i a j formam uma palavra, e você pergunta se o nó n é alcançável a partir do nó 0. Uma busca em largura com um conjunto de visitados faz 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 de modo que cada parte seja uma palavra 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 quantas vezes quiser, 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, cada uma quantas vezes quiser
Retornaboolean: true se s puder ser dividido em palavras do dicionário, false 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 não leva a lugar nenhum, pois nenhuma palavra começa com o er que sobra, então a primeira palavra que se encaixa nem sempre é a certa.

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: A string começa com pine + apple ou com pineapple, e ambos deixam tart. A única palavra que se encaixa ali é tar, que deixa um t isolado, então nenhum corte funciona.

+21 testes ocultos ao enviar

Para ir além

Retorne o menor número de palavras que uma segmentação válida pode usar, ou -1 se s não puder ser segmentada. 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

Cortar de forma gulosa falha nos dois sentidos: escolher primeiro a palavra mais curta divide sunflowerseed em sun + flow, e escolher primeiro a mais longa divide carpetal em carpet e deixa al sem correspondência. Então você precisa testar as opções, e uma string pode ser dividida de exponencialmente muitas maneiras. O que resolve o problema é que a possibilidade de dividir o restante da string depende apenas de onde esse restante começa, então há apenas n + 1 perguntas diferentes. 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

Leia s da esquerda. Seja qual for a primeira parte, ela precisa ser uma palavra com que s comece. Experimente cada palavra desse tipo e, para cada uma, faça a mesma pergunta sobre as letras restantes. Se alguma palavra levar a um corte completo, a resposta é true. Se nenhuma levar, é false. Quando não restar nada, você terá cortado todas as letras, então isso conta como sucesso.

Isso tenta todas as primeiras palavras possíveis, depois todas as segundas palavras possíveis e assim por diante, então não pode deixar passar um corte válido, e todo true retornado vem acompanhado de um corte real.

É lento porque verifica os mesmos trechos restantes repetidamente. Considere 299 cópias de a seguidas por um b, com as palavras a, aa e assim por diante até dez as. Toda maneira de dividir os a's em blocos de no máximo dez chega ao b e falha ali, e há mais de 10^89 maneiras desse tipo. A recursão precisa tentar todas antes de poder responder false.

Algoritmo

Escreva uma função auxiliar canSplit(start) que indique se as letras do índice start até o final podem ser divididas em palavras.
Se start for igual ao comprimento de s, retorne true.
Para cada palavra, verifique se s a contém começando no índice start.
Se contiver e canSplit(start + length of the word) for true, retorne true.
Se nenhuma palavra funcionar, 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 resto depende apenas de onde ele começa, e start assume apenas n + 1 valores. No exemplo com a's, o resto que começa no índice 20 é alcançado após dois blocos de dez, após vinte as individuais e de inúmeras outras maneiras, e a resposta é false todas as vezes. Armazene a resposta para cada posição inicial na primeira vez que a calcular e consulte-a depois.

Uma posição da memoização precisa de três estados: ainda não calculada, true e false. As respostas false são as que importam. Um true encerra toda a busca imediatamente, então o trabalho repetido pela recursão simples ocorre todo nos ramos que falham.

Cada posição inicial é calculada uma vez e testa todas as palavras, comparando até L letras, então o tempo é O(n × m × L): no máximo 300 × 1000 × 20 = 6 × 10^6 verificações de letras aqui. A memoização e a pilha de chamadas ocupam O(n) espaço, e as chamadas se aninham até 300 níveis.

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 fim da string e retorne a resposta armazenada se a posição de start contiver uma.
Caso contrário, tente cada palavra que começa em start, como na recursão simples, e pare na primeira cuja parte restante puder ser dividida.
Armazene o resultado na posição, incluindo false, e retorne-o.
Retorne 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)

De baixo para cima sobre prefixos com um conjunto de hash

Intuição

Inverta a abordagem e trabalhe com prefixos. Seja canEnd[i] uma indicação de se as primeiras i letras podem ser divididas em palavras. O prefixo vazio não precisa de palavras, então canEnd[0] é true. As primeiras end letras podem ser divididas exatamente quando a última parte delas, as letras de start a end, é uma palavra e as letras anteriores a ela podem ser divididas, isto é, canEnd[start] é true. Preencha a tabela da esquerda para a direita e todo canEnd[start] de que você precisa já será conhecido.

Em vez de comparar todas as m palavras em cada posição, coloque as palavras em um conjunto hash e procure as possíveis partes finais. Nenhuma palavra tem mais de L letras, então apenas as L partes que terminam em end podem corresponder. Em sunflowerseed, canEnd se torna true nas posições 0, 3 (sun), 7 (flow), 9 (flower) e 13 (seed após a posição 9), então a resposta é true. A posição 7 não leva a lugar nenhum, porque nenhuma palavra começa com er, e a tabela não se importa.

Há n posições, cada uma consulta no máximo L partes, e construir e calcular o hash de uma parte custa até L etapas. Isso dá O(n × L²), no máximo 300 × 20 × 20 = 1.2 × 10^5 etapas de processamento de letras, independentemente do tamanho do dicionário. A construção do conjunto lê cada palavra uma vez, O(m × L), então o total é O(m × L + n × L²). O conjunto armazena as palavras, O(m × L) letras, e a tabela armazena n + 1 sinalizadores. Não há recursão.

Algoritmo

Coloque cada palavra em um conjunto hash e anote o comprimento L da palavra mais longa.
Crie canEnd com n + 1 entradas, todas false, e defina canEnd[0] como true.
Para cada end de 1 a n, experimente 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 de testar comprimentos.
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

A maioria das respostas erradas acontece por escolher um corte cedo demais ou por fazer uma busca que nunca se lembra das falhas.

Cortar de forma gulosa. Escolher primeiro a palavra mais longa divide carpetal em carpet e deixa al, embora car + petal funcione. Escolher primeiro a mais curta falha com sunflowerseed.
Verificar apenas se cada letra de s aparece em alguma palavra. Com as palavras aaaa e aa, cada trecho tem comprimento par, então aaaaaaa, com sete letras, não pode ser dividido.
Armazenar no memo apenas as respostas true. Um true encerra a busca de qualquer forma. O trabalho repetido ocorre nos ramos false, então um memo sem eles continua tendo complexidade exponencial.
Criar a tabela com uma entrada a menos. canEnd[i] diz respeito às primeiras i letras, e tanto 0 quanto n são válidos, então são necessárias n + 1 entradas.
Comparar além do fim de s quando uma palavra é mais longa do que o trecho restante, como a palavra abc em relação a ab. Verifique os comprimentos antes de comparar as letras.
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 na letra e-k+1.

Perguntas frequentes4

Qual é a complexidade de tempo de Word Break?

A tabela de baixo para cima com um conjunto hash tem complexidade de tempo O(m × L + n × L²), em que n é o comprimento de s, m é o número de palavras e L é a palavra mais longa. A construção do conjunto lê cada palavra uma vez, e cada uma das n posições consulta no máximo L partes de até L letras. Se você comparar cada palavra em cada posição, em vez disso, a complexidade será O(n × m × L). A recursão simples sem memoização tem complexidade exponencial.

Por que uma abordagem gulosa falha no Word Break?

Uma regra gulosa se compromete com uma palavra e nunca reconsidera essa escolha. A estratégia de escolher primeiro a palavra mais longa divide carpetal em carpet e al, enquanto car + petal funciona. A estratégia de escolher primeiro a palavra mais curta divide sunflowerseed em sun + flow e fica presa em erseed. A programação dinâmica mantém todas as posições que podem ser alcançadas por algum corte, então nunca perde a posição correta.

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

As duas perspectivas funcionam. Na programação dinâmica, canEnd[i] indica se as primeiras i letras podem ser divididas, com base em prefixos menores. Como grafo, cada índice é um nó, com uma aresta de i a j quando as letras de i a j formam uma palavra, e você pergunta se o nó n é alcançável a partir do nó 0. Uma busca em largura com um conjunto de visitados faz o mesmo trabalho que a tabela.

Como listar cada frase em vez de retornar verdadeiro ou falso?

Use retrocesso: em cada índice, tente todas as palavras que se encaixam e faça uma chamada recursiva para o restante, construindo a frase conforme avança. Lembre-se da lista de frases para cada índice, para que o restante seja resolvido uma única vez. Execute primeiro 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.

Python

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

Casos de teste

Caso 1

Caso 2

Caso 3

Entrada

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

Esperado

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 sobre prefixos com um conjunto de hash

Armadilhas e casos extremos

Perguntas frequentes4

Problemas parecidos