24 de Março
Quebra de palavras
Como transformar segmentação de string em programacao dinamica de prefixos em vez de repetir a mesma tentativa em cada corte.
Programação Dinamica Intermediario 22 min TypeScript
Dada uma string s e um array wordDict, retorne true se s puder ser segmentada em uma ou mais palavras do dicionario.
Você pode reutilizar palavras do dicionario quantas vezes quiser.
Exemplo:
Input: s = "leetcode", wordDict = ["leet", "code"]
Output: true
O que perceber antes de codar
- O problema não pede listar todas as segmentacoes. Só pede saber se existe pelo menos uma.
- A pergunta natural vira sobre prefixos, não sobre a string inteira de uma vez.
- Busca rápida no dicionario ajuda muito.
Erros comuns
- repetir a mesma verificação de sufixo várias vezes na recursão
- manter o dicionario em array e pagar busca linear toda hora
Passo 1 - Entender o que esta sendo perguntado
O problema não quer todas as formas de quebrar a string.
Ele quer uma resposta booleana:
- existe alguma segmentação valida?
Isso já sugere que talvez você não precise carregar todas as combinações.
Passo 2 - Escrever a versão inicial recursiva
A versão inicial natural e:
- tentar cada corte possível
- se o prefixo atual estiver no dicionario, testar o resto
Funciona.
Mas repete muitos sufixos.
Passo 3 - Reformular como pergunta de prefixo
Em vez de perguntar "a string toda quebra?", você pode perguntar:
- os primeiros
icaracteres quebram?
Isso vira uma definição boa para DP:
dp[i] = trueses.slice(0, i)puder ser segmentada
Passo 4 - Descobrir a transição
Para que dp[i] seja verdadeiro, basta existir algum j < i tal que:
dp[j]já seja verdadeiros.slice(j, i)esteja no dicionario
Se isso acontecer, o prefixo até i também fecha.
O editor interativo precisa de JavaScript. Voce ainda pode ler o desafio e copiar o codigo inicial abaixo.
Codigo inicial
export function wordBreak(s: string, wordDict: string[]): boolean {
// sua solução aqui
return false
}
Ainda não resolveu?
Ver a solução agora pode reduzir o aprendizado. Vale a pena tentar mais um pouco.
Abrir a solucao de referencia
Sem JavaScript, a solucao de referencia aparece inline em vez de um dialogo.
Solução
Complexidade final
Tempo: O(n^2)
Espaço: O(n)
Solução 1 - Recursao tentando todos os cortes
Boa versão inicial para mostrar onde o retrabalho nasce.
export function wordBreak(s: string, wordDict: string[]): boolean {
function dfs(start: number): boolean {
if (start === s.length) {
return true
}
for (let end = start + 1; end <= s.length; end += 1) {
const candidate = s.slice(start, end)
if (wordDict.includes(candidate) && dfs(end)) {
return true
}
}
return false
}
return dfs(0)
}Funciona, mas reexplora muitos sufixos iguais.
Uma melhora intermediaria seria memorização: guardar a resposta de cada start para não resolver o mesmo sufixo duas vezes.
Solução 2 - Programacao dinamica de prefixos com conjunto hash em O(n^2)
Agora você guarda o que já sabe sobre cada prefixo.
export function wordBreak(s: string, wordDict: string[]): boolean {
const words = new Set(wordDict)
const dp = new Array(s.length + 1).fill(false)
dp[0] = true
for (let end = 1; end <= s.length; end += 1) {
for (let start = 0; start < end; start += 1) {
if (!dp[start]) {
continue
}
if (words.has(s.slice(start, end))) {
dp[end] = true
break
}
}
}
return dp[s.length]
}O ponto central e transformar “tentar todos os cortes” em “reaproveitar o que já sei sobre prefixos anteriores”.
No JavaScript, Set e a implementação prática desse conjunto hash para as palavras do dicionario.
O que dizer na entrevista
Uma explicação curta e boa seria:
A versão inicial recursiva tenta todos os cortes e repete a verificação dos mesmos sufixos várias vezes. A versão forte troca isso por DP de prefixos.
dp[i]diz se os primeirosicaracteres fecham. Entao eu testo se existe algumjcomdp[j] = truee substrings.slice(j, i)no dicionario.
Isso mostra que você:
- identificou o retrabalho
- escolheu uma definição de estado clara
- conectou a transição a uma pergunta simples
Quando esse padrão aparece de novo
Esse padrão reaparece quando você precisa:
- validar segmentação de string
- fazer DP sobre prefixos
- trocar tentativa recursiva por reaproveitamento de subproblemas
- combinar
programacao dinamicacom strings
O ponto não e decorar
Word Break.
O ponto e aprender a transformar cortes em estado de prefixo.