Самое длинное слово в словаре
Урок 13 из 14 курса Префиксные деревья (Trie) — Серия «Структуры данных» №8 на Coddy.
Дан словарь слов, найдите самое длинное слово, которое можно составить по одному символу за раз, добавляя их к слову, уже имеющемуся в словаре. "world" учитывается только в том случае, если "w", "wo", "wor" и "worl" также являются сохраненными словами.
Это идеальный случай для использования префиксного дерева (trie). Вставьте каждое слово, затем выполните DFS от корня — но переходите к дочернему узлу только в том случае, если он помечен как isEndOfWord. Таким образом, каждый узел, который мы посещаем во время DFS, представляет собой путь, где каждый префикс сам по себе является словом.
Отслеживайте самый длинный путь. Если два пути имеют одинаковую длину, выберите лексикографически меньший.
Задание
СреднеНапишите функцию longestWordInDict, которая принимает массив строк words и возвращает самое длинное слово, которое можно составить, добавляя по одному символу за раз к более короткому слову из этого массива.
Если два слова имеют одинаковую длину, верните лексикографически меньшее из них. Если массив пуст, верните пустую строку.
Вы должны использовать класс Trie (предоставленный в trie вместе с trienode) — не используйте встроенные средства языка, такие как множества (sets), словари (dicts) или карты (maps) для подсчета или отслеживания.
Попробуйте сами
#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;
}
Все уроки раздела Префиксные деревья (Trie) — Серия «Структуры данных» №8
3Практические задачи
Самый длинный общий префиксПодсчет слов с префиксомАвтодополнениеСамое длинное слово в словареРазбиение строки на слова