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

...

/

Solution Review: Insertion Count

Solution Review: Insertion Count

See the solution to the problem challenge.

We'll cover the following...

Solution

C++
Java
#include <iostream>

#include <vector>

#include <algorithm>

using namespace std;



// Definition of a trie node

class TrieNode

{

	public:

		// children array store pointer to TrieNode of next 52 alphabets (26 upper + 26 lower)

		TrieNode *children[52];

    	// A flag used to identify if a node denotes last character of a pattern

    	bool isEndOfPattern;

};



class Trie

{

	TrieNode * root;

	public:

		Trie()

		{

			root = new TrieNode();

		}



    	// inserts the pattern into the trie

    	void insert(string pattern)

    	{

    		// point the current node to root

    		TrieNode *curr = root;

    

    		// iterate all letters in the pattern

    		for (auto ch: pattern)

    		{

    			int idx = -1;

    

    			// if character is upper case

    			// calculate its index

    			//[A....Z] map to indexes[26...51]

    			if (ch >= 'A' && ch <= 'Z')

    				idx = 26 + ch - 'A';

    			else

    				idx = ch - 'a';

    

    			if (curr->children[idx] == NULL)

    				curr->children[idx] = new TrieNode();

    			curr = curr->children[idx];

    		}

    

    		// mark isEndOfPattern as "true"

    		// for the last node

    		curr->isEndOfPattern = true;

    	}

    

    	int countInsertions(string word)

    	{

    		// point the current node to root

    		TrieNode *curr = root;

    

    		// initialize a counter for calculating insertions

    		int insertions = 0;

    

    		// iterate all letters in the word

    		for (auto ch: word)

    		{

    			int idx = -1;

    			// if character is upper case

    			// it should be necessarily present

    			if (ch >= 'A' && ch <= 'Z')

    			{

    				idx = 26 + ch - 'A';

    				// if child node not found in trie, return -1

    				// if found, the move to the child node

    				if (curr->children[idx] == NULL)

    					return -1;

    				curr = curr->children[idx];

    			}

    			else

    			{

    				idx = ch - 'a';

    				// if character is lower case

    				// if found, the move to the child node

    				// else if not found, increment the insertion counter

    				if (curr->children[idx] != NULL)

    					curr = curr->children[idx];

    				else

    					insertions++;

    			}

    		}

    

    		// return the value of isEndOfPattern

    		// associated with the last node of the word

    		// value is "true" if pattern is completely matched

    		if (!curr->isEndOfPattern)

    			return -1;

    		return insertions;

    	}

};



vector<int> countPatternInsertions(vector<string> &words, string pattern)

{

	// Intialize a trie

	Trie *trie = new Trie();



	// insert the pattern into the trie

	trie->insert(pattern);



	vector<int> answer;



	// For all words, check if they match the pattern 

	for (int i = 0; i < words.size(); i++)

	{

		answer.push_back(trie->countInsertions(words[i]));

	}



	return answer;

}
Solution for problem challenge in C++

Intuition

This problem is an extension of pattern matching. Let's discuss the critical observations. First, the uppercase letters must be in the same order in the pattern as they appear in the word. The lowercase letters might or might not be part of the pattern. This problem deals with pattern matching in strings. As discussed in the introduction, tries can be an ideal candidate for solving this.

There are both uppercase and lowercase letters; therefore, an array of size 52 is used to store the child trie nodes. We store lowercase letters in the first 26 indexes and uppercase letters in the last 26 indexes. We will also include a boolean parameter, isEndOfPattern, to mark the ending of the pattern string in the trie.

C++
Java
// Definition of a trie node
class TrieNode
{
    public:
        // children array store pointer to TrieNode of 
        // next 52 alphabets (26 upper + 26 lower)
        TrieNode* children[52];
        // A flag used to identify if a node denotes 
        // last character of a pattern
        bool isEndOfPattern;
};
Definition of a trie node in C++

Algorithm

We initialize a variable insertions = 0 . This will keep the count of the total number of inserts to match the pattern. Then, for each word in the input, we iterate through the trie with characters in the word to check whether it matches the pattern. The procedure for handling uppercase and lowercase letters will be different here.

Case 1: Uppercase letters

If the character is an uppercase letter, check whether there exists a path with that character from the current trie node, which means that the trie node children array representing this letter is not null.

If the path does not exist, the letter is not present in the trie; therefore, the word does not match the pattern, and we can return -1. Otherwise, traverse down the node and move to the subsequent letter in the given word if a path exists.

Case 2: Lowercase letters

If the letter is lowercase, it's not necessarily present in the pattern. First, check whether the index in the trie node children array representing this letter is null. If it's not null, update the current trie node with the next trie node; otherwise, increment the insertions variable.

Following the above procedure, once the word is finished and we encounter a trie node with isEndOfPattern equal to true, we can conclude that the word matches the pattern and we can return the insertions counter. ...