Count Words With Prefix

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

How many stored words start with a given prefix? After inserting every word, walk from the root one character at a time along the prefix. If any character is missing, the answer is zero - no word could possibly start with that prefix.

If you reach the end of the prefix, you land on a node. Every stored word that begins with this prefix lives somewhere in the subtree rooted there. Count them by walking the subtree and adding 1 for every node where isEndOfWord is true.

Challenge

Easy

Write a function countWordsWithPrefix that gets a string array words and a string prefix, and returns the number of words in the array that start with the given prefix.

An empty prefix matches every word.

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"); }
    printf("%d\n", countWordsWithPrefix(words, n, prefix));
    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 PrefixCount Words With PrefixAutocomplete Longest Word In Dict Word Break