Search⌘ K
AI Features
Home
Courses
Data Structures for Coding Interviews in C++

Solution: Find All Words Stored in Trie

Explore how to retrieve all words stored in a trie by implementing recursive functions that traverse nodes and accumulate characters. Understand how depth-first search efficiently enumerates valid words, and learn about the time and space complexities involved in this solution.

We'll cover the following...

Statement

Given a trie data structure representing a list of words, implement a function that finds and returns all words stored in the trie.

Constraints:

  • 0≤0\leq words.length ≤103\leq 10^3

  • 1≤ 1\leq words[i].length ≤102\leq10^2

  • All words[i] consist of lowercase English letters.

Solution

This solution utilizes a trie data structure, efficiently organizing a list of words. In a trie, each word is broken down into letters, each represented by a node in the trie. Starting from the root node, each subsequent letter in the word corresponds to a child node of the previous letter’s node. This process continues until the entire word is represented by a path from the root node to a node marked as the end of the word. The algorithm explores each node by recursively traversing the trie from the root node, effectively enumerating all possible character combinations that form valid words. At each node, it checks if it marks the end of a word, constructing the word by accumulating characters from the word array. This recursive exploration continues until all words in the trie are found and stored in the result list. Let’s look at how each function behaves and contributes to this approach:

  • The findWords function recursively retrieves words from a tree structure. It initializes an empty list to store words and a list with a size determined by the tree’s maximum depth. As it traverses the tree, it retrieves the characters at each level to form words, appending them to the result list when a word is complete. Finally, it returns the list of extracted words.

  • The getWords function utilizes a depth-first search (DFS) approach to traverse a trie data structure. It starts from the given root node and recursively explores each branch. At each node, the algorithm checks if it marks the end of a word. If it does, it constructs the word by concatenating characters stored in the word array to the current level and adds it to the result list. Then, the algorithm iterates over the current node’s children, representing possible next characters in the words. For each child, it updates the word array with the character at the current level and recursively explores the child node. This process continues until all possible paths in the trie are explored, generating all words stored in the trie.

Let’s look at the illustration below to better understand the solution:

canvasAnimation-image
1 / 16

Let’s look at the code for this solution below:

C++
#include "Trie.cpp"
// Recursive function to find all the words stored in a trie
void getWords(TrieNode * root, vector < string > & result, int level, string & word) {
    // If the current node marks the end of a word, construct the word and append it to the result list
    if (root -> isEndWord) {
        string temp = "";
        for (int x = 0; x < level; x++) {
            temp += word[x];
        }
        result.push_back(temp);
    }
    for (int i = 0; i < 26; i++) {
        if (root -> children[i] != NULL) {
            // Update the word array with the character at the current level
            word[level] = (char)(i + 'a');
            
            // Recursively explore the child node
            getWords(root -> children[i], result, level + 1, word);
        }
    }
}
// Helper function to call the getWords function
vector < string > findWords(TrieNode * root) {
    vector <string> result;
    string word = "";
    getWords(root, result, 0, word);
    return result;
}
// Driver Code
int main() {
    int num = 1;
    vector<vector<string>> words = {
        {"gram", "groom", "ace", "act", "actor"},
        {"abs", "crow", "crop", "abstain", "crunch"},
        {"dorm", "norm", "prom", "loom", "room"},
        {"prey", "prep", "press", "preps", "prefix"},
        {"moon", "once", "face", "dice", "mole"}
    };
    for (auto word : words) {
        Trie t;
        for (auto w : word) {
            cout << "Insert word: '" << w << "'" << endl;
            t.insertNode(w);
            ++num;
        }
        auto words_found = findWords(t.root);
        cout << "\nWords found: [";
        for (auto word : words_found) {
            cout <<"'"<<word<<"' ";
        }
        cout << "]" << endl << string(100, '-') << endl;
    }
    return 0;
}

Complexity analysis

Time complexity

The time complexity of this solution is O(n)O(n), where nn is the total number of characters in all words stored in the trie. This complexity arises from traversing each trie node once to retrieve the words.

Space complexity

The space complexity of the provided code is O(n+m)O(n + m), where nn is the total number of characters in all words stored in the trie, and mm is the length of the longest word.