Advanced Data Structures: Implementing Tries in C++ and Java/

...

Solution Review: Composite Count

See the solution to the problem challenge.

We'll cover the following...

Solution
Complexity analysis

#include <iostream>
#include <vector>
using namespace std;

// Definition of a trie node
class TrieNode
{
    public:
       	// children array store pointer to TrieNode 
       	// of next 26 alphabets
        TrieNode *children[26];
        // a boolean flag to check if a node denotes 
        // end of a word
        bool isEndOfWord;
};

class Trie
{
    private:
        TrieNode * root;

    public:
        TrieNode* getRoot()
        {
            return root;
        }

        Trie()
        {
            root = new TrieNode();
        }
    
       	//insert a word into the trie
        void insert(string & word)
        {
            // point the current node to the root
            TrieNode* curr = root;
            for (int i = 0; i < word.size(); i++)
            {
                // find the index of the character
                // in the trie node's children array
                int index = word[i] - 'a';

                // create a new trie node
                // if child is not found
                if (curr->children[index] == nullptr)
                {
                    curr->children[index] = new TrieNode();
                }
    
                // move to the child node
                curr = curr->children[index];
            }
    
            // set isEndOfWord for the last trie node
            // of the word
            curr->isEndOfWord = true;
        }
};

int findCombinedWordCountRecursively(Trie *trie, string &word, int index)
{
   	// if last index of word is reached
   	// return true if count of smaller words 
   	// is greater than two
    int maxWordsCnt = 0;

    if (index == word.size())
        return maxWordsCnt;

    auto curr = trie->getRoot();

   	// Iterate through the characters of the word
    for (int i = index; i < word.size(); i++)
    {
       	// if node not found return false
       	// else move to the next node
        if (curr->children[word[i] - 'a'] == NULL)
            return maxWordsCnt;
        curr = curr->children[word[i] - 'a'];

       	// if end of one word is reached
       	// recursively check for the 
       	// remaining substring
        if (curr->isEndOfWord)
        {
            maxWordsCnt = max(maxWordsCnt, 1 + findCombinedWordCountRecursively(trie, word, i + 1));
        }
    }

   	// return maxWordsCnt as answer
    return maxWordsCnt;
}

vector<int> findCompositeCount(vector<string> &words)
{
   	// initialize a trie
   	// by inserting words
    Trie *trie = new Trie();
    for (auto w: words)
        trie->insert(w);
    vector<int> result;

   	// iterate through the input words
    for (auto &word: words)
    {
        int index = 0;

       	// if the words is a combination 
       	// of many words, add to the result
        int maxWordCount = 0;
        int ans = findCombinedWordCountRecursively(trie, word, index);
        result.push_back(ans);
    }

    return result;
}

Solution for problem challenge in C++

Intuition

This problem is an extension of combined words. Observing the examples, we can see that a combined word is created by adding other words as prefixes. Let's consider the word W and divide it into two parts at an index, i. Let's call the substring from index 0 to i as P and the substring from i+1 to length(w) as S. If we can find P word in the given list of words, it means that we've found a valid prefix for the word S. Now we can move ahead and break down the word S into more such substrings and extract smaller words out of it.

So, essentially, we have to answer this question recursively each time: is a substring(word[i, word. length()-1]) prefixed with another word given in the list of words? Because we consider the smaller words as prefixes to the combined word, the trie data structure can naturally help us identify valid combined words.

To summarize, we iterate through the letters of the word, finding the nodes in the trie, until we encounter a node with isEndOfWord set as true. This implies that we've found a shorter valid word in the given word, so we increment the count of words and then follow the same search procedure recursively for the remaining substring from the start of the trie.

Let's dive into an example, where words list = {"pen", "pens", "ink","pensinkpens", "inkpensink"} and we try to find other small words present in pensinkpens.

We call a search method search("pensinkpens", 0) , which results in two possible paths:

We can consider one of the smaller words as pen and further perform a search for the string sinkpens.
We can consider pens as the word and perform a search for inkpens.

The first path leads to no valid answers since sinkpens cannot be broken down further into smaller words. The second path leads to finding one word (inkpens) increasing the combined words count to 1, and then performing search("inkpens", 1), which leads to another word (ink) being found. The combined word now count increases to 2, and then a call to search("pens", 2) again results in the word pens being found and leads to the combined words count increasing to 3. The entire word string is thus divided into three smaller words ("pens" + "ink" + "pens") successfully.

Algorithm

Step 1: Insert the words into a trie

Insert all the words into a trie. Then, iterate again over the list and traverse the trie for each word to calculate the number of shorter words in a combined word recursively.

Step 2: Recursively check for prefixes

Move from the root node downward with each character in the word; if you encounter isEndOfWord = true, it means that a valid prefix has been traversed. We can now jump to the root node and keep moving forward in the word or ignore the isEndOfWord flag and keep moving in the word forward without jumping to the trie root node. We make both of these calls recursively.

Once the word ends, we check if the trie traversal finishes on a valid word—that is, for the current trie node, we check if isEndOfWord = true. If it doesn't, then it's not a combined word and we return false. If it does, we check the number of times we've previously seen a valid prefix for the current word; if it's more than once, it's a combined word.

Visualization

The diagram below represents the procedure in detail.

Access this course and 1400+ top-rated courses and projects.

Preview Free Lessons→

Preview Free Lessons

Introduction to Tries

Prefix Search

Suffix Search

Bitwise Tries

Pattern Matching

File Systems

Trie Traversal

Search Engine

Miscellaneous

Conclusion

Solution Review: Composite Count

Solution

Intuition

Algorithm

Visualization

Complexity analysis

Variables