Solution Review: Search Similar Words

#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 + 1 special character
		TrieNode *children[27];
    	// A flag used to identify if a 
    	// node denotes last character of a word
    	bool isEndOfWord;
    	// a vector to store the complete word
    	// at the last node of each path
    	// this helps in easy retrieval of words
    	vector<string> words;
};

class Trie
{
	public:
		TrieNode * root;
    	Trie()
    	{
    		root = new TrieNode();
    	}
    
    	// insert a word into trie
    	void insert(string word, string completeWord)
    	{
    		// point the current node to the root
    		TrieNode *curr = root;
    		for (char curChar: word)
    		{
    			int idx = 26;
    			if (curChar != '_')
    			{
    				idx = curChar - 'a';
    			}
    
    			//create a new trie node
    			// if not already existing in trie
    			if (curr->children[idx] == NULL)
    			{
    				curr->children[idx] = new TrieNode();
    			}
    
    			curr = curr->children[idx];
    		}
    
    		//mark isEndOfWord as true for the last node
    		curr->isEndOfWord = true;
    		curr->words.push_back(completeWord);
    	}
    
    	// search a word into trie
    	vector<string> search(string word)
    	{
    		// point the current node to the root
    		TrieNode *curr = root;
    
    		// iterate through all characters of the given word
    		for (char curChar: word)
    		{
    			int idx = 26;
    			if (curChar != '_')
    			{
    				idx = curChar - 'a';
    			}
    
    			// if a character in the word is not found, return false
    			if (curr->children[idx] == NULL)
    			{
    				return {};
    
    			}
    
    			curr = curr->children[idx];
    		}
    
    		// return the value of isEndOfWord for the last character of the word being searched
    		// if isEndOfWord is true, it means word was found completely
    		// else false if returned
    		return curr->words;
    	}
};

// replaces all indexes by special character "_" 
// one by one and push to a result vector
vector<string> addSpecialCharAtAllIndexes(string word)
{
	vector<string> result;
	int len = word.size();
	for (int index = 0; index < len; index++)
	{
		char temp = word[index];
		word[index] = '_';
		result.push_back(word);
		word[index] = temp;
	}

	return result;
}

vector<int> queryMatchingWordsCount(vector<string> words, vector<string> queryWords)
{
	// Initialise a trie
	Trie *trie = new Trie();

	// Iterate through the words
	for (string word: words)
	{
		vector<string> oneCharAwayStrings = addSpecialCharAtAllIndexes(word);

		//insert the words oneCharAwayStrings in trie
		for (string oneCharAwayString: oneCharAwayStrings)
		{
			trie->insert(oneCharAwayString, word);
		}
	}

	vector<int> result;
	// Iterate through the query words
	for (string queryWord: queryWords)
	{
		vector<string> resultForQueryWord;
		// find all one character away words for given query word
		// check if any of those exist in the trie
		vector<string> oneCharAwayStrings = addSpecialCharAtAllIndexes(queryWord);
		for (string oneCharAwayString: oneCharAwayStrings)
		{
			vector<string> nearByWords = trie->search(oneCharAwayString);
			for (string s: nearByWords)
				resultForQueryWord.push_back(s);
		}

		result.push_back(resultForQueryWord.size());
	}

	return result;
}