Longest Common Prefix

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

The next challenges are designed to use a Trie in them.

Use the Trie and TrieNode classes you built in the previous lessons (they are provided for you in the files on the left). Each challenge ships you a fresh solution file where you write a function that USES the Trie.

Our first problem: given a list of words, find the longest common prefix they all share. After inserting every word into a trie, the answer is the path from the root downward as long as exactly one child exists at each step and no node is end-of-word.

Challenge

Easy

Write a function longestCommonPrefix that gets a string array words and returns the longest string that is a prefix of every word in the array.

If the array is empty, or no common prefix exists, 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 = longestCommonPrefix(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 PrefixCount Words With Prefix Autocomplete Longest Word In Dict Word Break