Adicionar e buscar palavras com árvore de prefixos (trie)

Solução 1 - Array de palavras com busca linear

Bom ponto de partida porque resolve o problema sem mudar a estrutura de dados.

export function runWordDictionary(operations, values) {
  const words = []
  const result = []

  function matches(pattern, word) {
    if (pattern.length !== word.length) {
      return false
    }

    for (let index = 0; index < pattern.length; index += 1) {
      if (pattern[index] !== "." && pattern[index] !== word[index]) {
        return false
      }
    }

    return true
  }

  for (let index = 0; index < operations.length; index += 1) {
    const operation = operations[index]
    const value = values[index]

    if (operation === "WordDictionary") {
      result.push(null)
    } else if (operation === "addWord") {
      words.push(value)
      result.push(null)
    } else if (operation === "search") {
      result.push(words.some((word) => matches(value, word)))
    }
  }

  return result
}

Ela funciona.

Mas toda busca passa pela lista inteira, mesmo quando várias palavras compartilham prefixo.

Solução 2 - Árvore de prefixos (trie) com busca em profundidade (DFS) para curinga

Agora a estrutura conversa com o problema:

• addWord desce pela árvore criando nos
• search faz busca guiada pelo padrão
• . abre vários ramos, mas só a partir do no atual

type TrieNode = {
  children: Map<string, TrieNode>
  isWord: boolean
}

function createNode(): TrieNode {
  return {
    children: new Map(),
    isWord: false,
  }
}

export function runWordDictionary(operations, values) {
  const root = createNode()
  const result = []

  function addWord(word: string) {
    let node = root

    for (const char of word) {
      if (!node.children.has(char)) {
        node.children.set(char, createNode())
      }

      node = node.children.get(char)!
    }

    node.isWord = true
  }

  function search(word: string): boolean {
    function dfs(node: TrieNode, index: number): boolean {
      if (index === word.length) {
        return node.isWord
      }

      const char = word[index]

      if (char !== ".") {
        const next = node.children.get(char)
        return next ? dfs(next, index + 1) : false
      }

      for (const next of node.children.values()) {
        if (dfs(next, index + 1)) {
          return true
        }
      }

      return false
    }

    return dfs(root, 0)
  }

  for (let index = 0; index < operations.length; index += 1) {
    const operation = operations[index]
    const value = values[index]

    if (operation === "WordDictionary") {
      result.push(null)
    } else if (operation === "addWord") {
      addWord(value)
      result.push(null)
    } else if (operation === "search") {
      result.push(search(value))
    }
  }

  return result
}

O ponto forte não e só “usar uma árvore de prefixos”.

E perceber que o curinga não pede comparar tudo.

Ele pede ramificar só quando realmente encontra ..

O que dizer na entrevista

Uma explicação curta e boa seria:

A versão inicial guarda palavras num array e, em cada busca, compara tudo caractere por caractere. Isso funciona, mas ignora prefixos compartilhados. A versão forte usa uma árvore de prefixos para guardar esses prefixos uma vez só. Em search, caractere normal segue um único filho e . vira uma busca em profundidade (DFS) pelos filhos do no atual. Assim a estrutura reflete exatamente a regra do problema.

Isso mostra que você:

• pensou na estrutura certa para prefixo
• entendeu o custo do curinga
• explicou por que a busca em profundidade (DFS) aparece
• adaptou a interface orientada a classe para o formato usado aqui

Quando esse padrão aparece de novo

A mesma ideia volta quando o problema pede:

• busca por prefixo
• autocomplete
• dicionario de palavras
• curinga por caractere

Se a pergunta central for “como aproveitar prefixos em comum?”, uma árvore de prefixos entra forte na conversa.