Prefijo común más largo

Lección 10 de 14 del curso Tries - Serie de Estructuras de Datos #8 de Coddy.

Los siguientes desafíos están diseñados para usar un Trie en ellos.

Usa las clases Trie y TrieNode que construiste en las lecciones anteriores (se te proporcionan en los archivos de la izquierda). Cada desafío te entrega un nuevo archivo solution donde escribes una función que USA el Trie.

Nuestro primer problema: dada una lista de palabras, encuentra el prefijo común más largo que todas comparten. Después de insertar cada palabra en un trie, la respuesta es el camino desde la raíz hacia abajo siempre que exista exactamente un hijo en cada paso y ningún nodo sea el final de una palabra.

Desafío

Fácil

Escribe una función longestCommonPrefix que reciba un arreglo de cadenas words y devuelva la cadena más larga que sea un prefijo de cada palabra en el arreglo.

Si el arreglo está vacío, o no existe un prefijo común, devuelve una cadena vacía.

Debes usar la clase Trie (proporcionada en trie junto con trienode); no utilices funciones integradas del lenguaje como conjuntos, diccionarios o mapas para contar o rastrear.

Pruébalo tú mismo

#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 las lecciones de Tries - Serie de Estructuras de Datos #8

1Introducción

Introducción ¿Qué es un Trie?

2Proyecto Trie

Clase TrieNode Clase Trie Insertar Buscar Empieza con Eliminar Conteo de palabras

3Desafíos de práctica

Prefijo común más largoContar palabras con prefijo Autocompletado Palabra más larga en el diccionario División de palabras