24 de Março
Busca de palavra
Como explorar caminhos em uma grade, marcar a escolha atual e desfazer a decisão ao voltar da busca.
Backtracking Intermediario 25 min TypeScript
Dada uma matriz board de letras e uma string word, retorne true se a palavra puder ser formada por letras adjacentes na grade.
As letras podem ser conectadas horizontalmente ou verticalmente.
A mesma celula não pode ser usada mais de uma vez no mesmo caminho.
Exemplo:
Input:
board = [
["A","B","C","E"],
["S","F","C","S"],
["A","D","E","E"]
]
word = "ABCCED"
Output: true
O que perceber antes de codar
- O problema não pede o menor caminho. Pede saber se existe pelo menos um caminho valido.
- O estado de "visitado" pertence ao caminho atual, não ao board inteiro para sempre.
- Backtracking aqui e exatamente tentar, marcar, explorar e desfazer.
Erros comuns
- compartilhar o mesmo conjunto de visitados entre tentativas independentes
- esquecer de desfazer a marca ao voltar da recursão
Passo 1 - Entender o que precisa ser controlado
O problema não e "andar na grade" apenas.
O problema e:
- andar na grade seguindo a proxima letra certa
- sem reutilizar a mesma celula no mesmo caminho
Isso já tem cara de busca em profundidade (DFS) com backtracking.
Passo 2 - Escrever a versão inicial mais direta
A versão inicial natural e:
- tentar cada celula como começo
- fazer
busca em profundidade (DFS) - guardar um
conjunto hashcom as coordenadas visitadas no caminho atual
Funciona e deixa o raciocínio bem visível.
Passo 3 - Perguntar onde esta o estado de verdade
O "visitado" não e global.
Ele só vale para a tentativa atual.
Se um caminho falhar, as outras tentativas devem poder reutilizar aquelas celulas.
Por isso backtracking precisa desfazer a marca ao voltar.
Passo 4 - Simplificar a estrutura auxiliar
Em vez de manter um conjunto de visitados separado, da para marcar a própria celula temporariamente e depois restaurar.
O efeito logico e o mesmo:
- marca
- explora
- desfaz
Só que com menos custo por chamada.
O editor interativo precisa de JavaScript. Voce ainda pode ler o desafio e copiar o codigo inicial abaixo.
Codigo inicial
export function exist(board: string[][], word: 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(rows * cols * 4^word.length)
Espaço: O(word.length)
Solução 1 - Busca em profundidade (DFS) com conjunto hash de visitados
Boa versão inicial porque deixa o estado do caminho explícito.
export function exist(board: string[][], word: string): boolean {
const rows = board.length
const cols = board[0].length
function dfs(row: number, col: number, index: number, visited: Set<string>): boolean {
if (index === word.length) {
return true
}
const outOfBounds = row < 0 || row >= rows || col < 0 || col >= cols
if (outOfBounds || board[row][col] !== word[index]) {
return false
}
const key = `${row},${col}`
if (visited.has(key)) {
return false
}
visited.add(key)
const found =
dfs(row + 1, col, index + 1, visited) ||
dfs(row - 1, col, index + 1, visited) ||
dfs(row, col + 1, index + 1, visited) ||
dfs(row, col - 1, index + 1, visited)
visited.delete(key)
return found
}
for (let row = 0; row < rows; row += 1) {
for (let col = 0; col < cols; col += 1) {
if (dfs(row, col, 0, new Set())) {
return true
}
}
}
return false
}Funciona, mas o conjunto de visitados adiciona trabalho extra em toda chamada.
Solução 2 - Backtracking marcando a grade no lugar
Agora o estado continua local ao caminho, mas sem estrutura auxiliar de coordenadas.
export function exist(board: string[][], word: string): boolean {
const rows = board.length
const cols = board[0].length
function dfs(row: number, col: number, index: number): boolean {
if (index === word.length) {
return true
}
const outOfBounds = row < 0 || row >= rows || col < 0 || col >= cols
if (outOfBounds || board[row][col] !== word[index]) {
return false
}
const current = board[row][col]
board[row][col] = "#"
const found =
dfs(row + 1, col, index + 1) ||
dfs(row - 1, col, index + 1) ||
dfs(row, col + 1, index + 1) ||
dfs(row, col - 1, index + 1)
board[row][col] = current
return found
}
for (let row = 0; row < rows; row += 1) {
for (let col = 0; col < cols; col += 1) {
if (dfs(row, col, 0)) {
return true
}
}
}
return false
}O insight forte aqui não e só “usar recursão”. E controlar o estado certo no lugar certo com busca em profundidade (DFS) e backtracking.
O que dizer na entrevista
Uma explicação curta e boa seria:
Eu testo cada celula como ponto de partida e faco
busca em profundidade (DFS)para casar a palavra letra por letra. O cuidado principal e não reutilizar a mesma celula no caminho atual. Por isso marco a escolha antes de explorar os vizinhos e desfaco ao voltar. Essa parte de desfazer e o própriobacktracking.
Isso mostra que você:
- entendeu o papel do estado local
- sabe explicar por que precisa desfazer
- não trata backtracking como magia
Quando esse padrão aparece de novo
Esse padrão reaparece quando você precisa:
- explorar muitos caminhos possiveis
- manter restrições locais por tentativa
- marcar e restaurar estado em
busca em profundidade (DFS) - resolver grade, combinações ou busca com poda
O ponto não e decorar esse problema.
O ponto e aprender que backtracking e explorar com disciplina, não tentar tudo no escuro.