24 de Março
Dicionário alienígena
Como extrair restrições entre letras a partir de palavras ordenadas e transformar isso em ordenacao topologica.
Grafos Avancado 30 min TypeScript
Dado um array de palavras words que já esta ordenado segundo a ordem alfabetica de uma língua alienigena, retorne uma string com uma ordem valida das letras.
Regras:
- se a entrada for inválida, retorne
"" - se existir mais de uma ordem valida, aqui no SeniorPath retorne a lexicograficamente menor para manter a comparação deterministica
Exemplo:
Input: words = ["wrt","wrf","er","ett","rftt"]
Output: "wertf"
O que perceber antes de codar
- As arestas nascem da primeira diferença entre duas palavras vizinhas.
- Se uma palavra maior vier antes do próprio prefixo, a entrada e inválida.
- Letras sem arestas também precisam aparecer na resposta.
Erros comuns
- continuar comparando caracteres depois da primeira diferença
- esquecer o caso inválido tipo `["abc", "ab"]`
Passo 1 - Entender de onde vem a informação
O problema não te da pares de letras diretamente.
Ele te da:
- palavras já ordenadas
Entao você precisa extrair restrições dessa ordem.
Passo 2 - Ver qual comparação realmente importa
Entre duas palavras vizinhas, a ordem da língua só revela uma coisa:
- o primeiro caractere em que elas diferem
Exemplo:
"wrt""wrf"
A primeira diferença e t vs f.
Entao sabemos:
tvem antes def
Depois disso, o resto não importa para esse par.
Passo 3 - Tratar o caso inválido cedo
Se aparecer:
"abc""ab"
Isso e impossivel.
Porque a palavra maior não pode vir antes do próprio prefixo se a lista esta em ordem lexicografica.
Passo 4 - Transformar restrições em grafo
Depois de extrair as arestas, o problema vira:
- achar uma ordem linear que respeite todas as dependências
Isso e ordenacao topologica.
O editor interativo precisa de JavaScript. Voce ainda pode ler o desafio e copiar o codigo inicial abaixo.
Codigo inicial
export function alienOrder(words: string[]): string {
// sua solução aqui
return ""
}
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(C + V log V + E)
Espaço: O(V + E)
Solução 1 - Grafo mais busca em profundidade (DFS) com estados
Boa versão inicial porque deixa visíveis as duas partes: construir restrições e detectar ciclo.
export function alienOrder(words: string[]): string {
const graph = new Map<string, Set<string>>()
for (const word of words) {
for (const char of word) {
if (!graph.has(char)) {
graph.set(char, new Set())
}
}
}
for (let index = 0; index < words.length - 1; index += 1) {
const first = words[index]
const second = words[index + 1]
if (first.length > second.length && first.startsWith(second)) {
return ""
}
const limit = Math.min(first.length, second.length)
for (let charIndex = 0; charIndex < limit; charIndex += 1) {
const from = first[charIndex]
const to = second[charIndex]
if (from !== to) {
graph.get(from)!.add(to)
break
}
}
}
const state = new Map<string, number>()
const order: string[] = []
function dfs(char: string): boolean {
if (state.get(char) === 1) {
return false
}
if (state.get(char) === 2) {
return true
}
state.set(char, 1)
for (const neighbor of graph.get(char)!) {
if (!dfs(neighbor)) {
return false
}
}
state.set(char, 2)
order.push(char)
return true
}
for (const char of graph.keys()) {
if (!dfs(char)) {
return ""
}
}
return order.reverse().join("")
}Funciona.
Mas aqui ainda falta garantir uma ordem deterministica quando várias letras estao liberadas ao mesmo tempo.
Solução 2 - Kahn com grau de entrada e fila ordenada
Agora a ordem sai de forma controlada.
export function alienOrder(words: string[]): string {
const graph = new Map<string, Set<string>>()
const indegree = new Map<string, number>()
for (const word of words) {
for (const char of word) {
if (!graph.has(char)) {
graph.set(char, new Set())
indegree.set(char, 0)
}
}
}
for (let index = 0; index < words.length - 1; index += 1) {
const first = words[index]
const second = words[index + 1]
if (first.length > second.length && first.startsWith(second)) {
return ""
}
const limit = Math.min(first.length, second.length)
for (let charIndex = 0; charIndex < limit; charIndex += 1) {
const from = first[charIndex]
const to = second[charIndex]
if (from !== to) {
if (!graph.get(from)!.has(to)) {
graph.get(from)!.add(to)
indegree.set(to, indegree.get(to)! + 1)
}
break
}
}
}
const available = [...graph.keys()].filter((char) => indegree.get(char) === 0).sort()
const order: string[] = []
while (available.length > 0) {
const char = available.shift()!
order.push(char)
for (const neighbor of [...graph.get(char)!].sort()) {
indegree.set(neighbor, indegree.get(neighbor)! - 1)
if (indegree.get(neighbor) === 0) {
available.push(neighbor)
}
}
available.sort()
}
return order.length === graph.size ? order.join("") : ""
}O insight forte aqui e que a ordem alienigena não e adivinhada. Ela e derivada de restrições e validada por ausencia de ciclo.
O que dizer na entrevista
Uma explicação curta e boa seria:
Eu comparo palavras vizinhas e pego só a primeira diferença, porque e ela que cria uma restrição entre letras. Depois construo um grafo dirigido e resolvo com
ordenacao topologica. Também trato cedo o caso de prefixo inválido, comoabcantes deab, porque isso já torna a entrada impossivel.
Isso mostra que você:
- soube extrair restrições da entrada
- traduziu o problema para o modelo certo
- cobriu tanto ciclo quanto prefixo inválido
Quando esse padrão aparece de novo
Esse padrão reaparece quando você precisa:
- deduzir ordem a partir de comparações parciais
- transformar regras em arestas dirigidas
- usar
ordenacao topologicapara encontrar ordem valida - perceber que “ordem parcial” não e a mesma coisa que “ordem adivinhada”
O ponto não e decorar esse problema.
O ponto e aprender a construir o grafo certo a partir das pistas certas.