Autocomplete

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

This is the classic use case for a trie: given what the user has typed so far, list every stored word that begins with that prefix. Walk to the prefix node; if you cannot, return nothing. Then explore the subtree below and collect every word you find.

As you walk down during the DFS, build the word incrementally by appending the character of the edge you just crossed. Each time you hit a node where isEndOfWord is true, the current path is one of the matches.

Challenge

Medium

Write a function autocomplete that gets a string array words and a string prefix, and returns the list of words from the array that start with prefix.

The returned list must be in ascending (alphabetical) order. If no word matches, return an empty list.

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 l1[4096], prefix[1024];
    if (!fgets(l1, sizeof(l1), stdin)) l1[0] = 0;
    if (!fgets(prefix, sizeof(prefix), stdin)) prefix[0] = 0;
    l1[strcspn(l1, "\r\n")] = '\0';
    prefix[strcspn(prefix, "\r\n")] = '\0';
    char* words[1024]; int n = 0;
    char* tok = strtok(l1, " \t");
    while (tok && n < 1024) { words[n++] = tok; tok = strtok(NULL, " \t"); }
    int out_n = 0;
    char** res = autocomplete(words, n, prefix, &out_n);
    for (int i = 0; i < out_n; i++) { printf("%s", res[i]); if (i + 1 < out_n) printf(" "); }
    printf("\n");
    if (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 PrefixAutocompleteLongest Word In Dict Word Break