Longest Word In Dict

Lesson 13 of 14 in Coddy's Tries - Data Structures Series #8 course.

Given a dictionary of words, find the longest word that can be built up one character at a time by appending to a word already in the dictionary. "world" only counts if all of "w", "wo", "wor", and "worl" are also stored words.

This is a perfect fit for a trie. Insert every word, then DFS from the root - but only descend into a child if it is marked isEndOfWord. That way, every node we visit during the DFS represents a path where every prefix is itself a word.

Track the longest path. If two paths have the same length, pick the lexicographically smaller one.

Challenge

Medium

Write a function longestWordInDict that gets a string array words and returns the longest word that can be built by appending one character at a time to a shorter word in the array.

If two words tie on length, return the lexicographically smaller one. If the array is empty, return an empty string.

You must use the Trie class (provided in trie along with trienode) - do not use language built-ins like sets, dicts, or maps to count/track.

Try it yourself

#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;
}

All lessons in Tries - Data Structures Series #8

1Introduction

Introduction What is a Trie?

2Trie Project

TrieNode Class Trie Class Insert Search StartsWith Delete WordCount

3Practice Challenges

Longest Common Prefix Count Words With Prefix AutocompleteLongest Word In DictWord Break