Prefixo Comum Mais Longo
Lição 10 de 14 do curso Tries - Série de Estruturas de Dados #8 da Coddy.
Os próximos desafios foram projetados para usar uma Trie neles.
Use as classes Trie e TrieNode que você construiu nas lições anteriores (elas são fornecidas para você nos arquivos à esquerda). Cada desafio fornece a você um novo arquivo solution onde você escreve uma função que USA a Trie.
Nosso primeiro problema: dada uma lista de palavras, encontre o prefixo comum mais longo que todas elas compartilham. Após inserir cada palavra em uma trie, a resposta é o caminho da raiz para baixo, desde que exista exatamente um filho em cada etapa e nenhum nó seja o fim de uma palavra.
Desafio
FácilEscreva uma função longestCommonPrefix que recebe um array de strings words e retorna a string mais longa que é um prefixo de cada palavra no array.
Se o array estiver vazio, ou se não existir um prefixo comum, 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 contagem/rastreamento.
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 = longestCommonPrefix(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