Maior Palavra no Dicionário
Lição 13 de 14 do curso Tries - Série de Estruturas de Dados #8 da Coddy.
Dado um dicionário de palavras, encontre a palavra mais longa que pode ser construída um caractere por vez ao anexar a uma palavra que já está no dicionário. "world" só conta se todas as palavras "w", "wo", "wor" e "worl" também forem palavras armazenadas.
Isso se encaixa perfeitamente em uma trie. Insira cada palavra e, em seguida, faça uma DFS a partir da raiz - mas apenas desça para um filho se ele estiver marcado como isEndOfWord. Dessa forma, cada nó que visitamos durante a DFS representa um caminho onde cada prefixo é, por si só, uma palavra.
Rastreie o caminho mais longo. Se dois caminhos tiverem o mesmo comprimento, escolha o lexicograficamente menor.
Desafio
MédioEscreva uma função longestWordInDict que recebe um array de strings words e retorna a palavra mais longa que pode ser construída anexando um caractere de cada vez a uma palavra mais curta no array.
Se duas palavras empatarem no comprimento, retorne a lexicograficamente menor. Se o array estiver vazio, retorne uma string vazia.
Você deve usar a classe Trie (fornecida em trie junto com trienode) - não use recursos integrados da linguagem como sets, dicts ou maps para contar/rastrear.
Experimente você mesmo
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include "solution.h"
int main() {
char line[4096];
if (!fgets(line, sizeof(line), stdin)) line[0] = 0;
line[strcspn(line, "\r\n")] = '\0';
char* words[1024]; int n = 0;
char* tok = strtok(line, " \t");
while (tok && n < 1024) { words[n++] = tok; tok = strtok(NULL, " \t"); }
char* res = longestWordInDict(words, n);
printf("%s\n", res);
free(res);
return 0;
}
Todas as lições de Tries - Série de Estruturas de Dados #8
3Desafios Práticos
Prefixo Comum Mais LongoContar Palavras com PrefixoAutocompletarMaior Palavra no DicionárioQuebra de Palavras