Gain insights into trie data structures, their implementation in C++ and Java, and their application in solving algorithmic problems and designing complex systems, enhancing your software engineering skills.

edited - Advanced Data Structures - TRIES.png

Trie is an efficient tree-like data structure used to store and retrieve information. It is frequently tested in coding interviews, indicating its widespread use in solving many real-world software engineering challenges.

This course covers every aspect of the trie data structure, from the intuition of building a trie to coding it in famous programming languages for solving algorithmic problems and designing real-world systems. It assumes a prior knowledge of trees and basic data structures like lists and arrays. 

The problems in this course are categorized into various patterns, which will help you map new solutions to known issues using tries. The problems are of varying difficulties, from easy to hard, thus giving you an iterative learning experience. By the end of this course, you’ll be able to decode relevant trie problems, code their solutions in C++ and Java, and apply trie concepts to design complex software systems.

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

words: ["app", "apple", "apply", "applicable"]
pref: "a"
suff: "y"

words: ["app", "apple", "apply", "applicable"]
pre: "a"
suff: "e"

#include <iostream>
#include <vector>
using namespace std;

int findWordsWithPrefAndSuff(vector<string>& words, string pref, string suff) {
  // your code goes here
  return -1;
}

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

// Definition of a TrieNode
class TrieNode
{
	public:
		// children array store pointer to TrieNode of next 26 alphabets
		TrieNode *children[26];
    	// A flag used to identify the end of word nodes or leaf nodes
    	bool isEndOfWord;
    	// A list to store the indices of the words
    	// passing through the trie node 
    	vector<int> indices;

};

class PrefixTrie
{
	public:

		// Intialise the root of prefix trie
		TrieNode * root;
    	PrefixTrie()
    	{
    		root = new TrieNode();
    	}
    
    	void insert(string &word, int index)
    	{
    		// point the current node as root
    		TrieNode *curr = root;
    
    		for (int i = 0; i < word.length(); i++)
    		{
    			// add the index of the given word
    			// to the indices array of current node
    			(curr->indices).push_back(index);
    
    			char c = word[i];
    
    			//create a new trie node
    			// if child link is not found
    			if (curr->children[c - 'a'] == nullptr)
    			{
    				curr->children[c - 'a'] = new TrieNode();
    			}
    
    			curr = curr->children[c - 'a'];
    		}
    
    		//set the value of isEndOfWord for last node
    		// in the path
    		curr->isEndOfWord = true;
    		(curr->indices).push_back(index);
    	}
    
    	vector<int> search(string & word)
    	{
    		// point the current node as root
    		TrieNode *curr = root;
    
    		for (int i = 0; i < word.length(); i++)
    		{
    			// if child link is not found
    			// it means prefix does not exists
    			// return empty indices array
    
    			if (curr->children[word[i] - 'a'] == nullptr)
    			{
    				return {};
    
    			}
    
    			curr = curr->children[word[i] - 'a'];
    		}
    
    		// if prefix is found completely
    		// return indices associated with
    		// last node in the path
    		return curr->indices;
    	}
};

// All operations performed in suffix trie
// are similar except the fact
// that strings are processed in reverse order
// both in insertion and searching

class SuffixTrie
{
	public:
		TrieNode * root;
	SuffixTrie()
	{
		root = new TrieNode();
	}

	void insert(string &word, int index)
	{
		TrieNode *curr = root;
		for (int i = word.length() - 1; i >= 0; i--)
		{ (curr->indices).push_back(index);
			char c = word[i];
			if (curr->children[c - 'a'] == nullptr)
			{
				curr->children[c - 'a'] = new TrieNode();
			}

			curr = curr->children[c - 'a'];
		}

		(curr->indices).push_back(index);
		curr->isEndOfWord = true;
	}

	vector<int> search(string & word)
	{
		TrieNode *curr = root;
		for (int i = word.length() - 1; i >= 0; i--)
		{
			char c = word[i];
			if (curr->children[c - 'a'] == nullptr)
			{
				return {};

			}

			curr = curr->children[c - 'a'];
		}

		return curr->indices;
	}
};

int findWordsWithPrefAndSuff(vector<string> &words, string prefix, string suffix)
{
	// Intialise a prefix and a suffix trie seperately
	PrefixTrie * pTrie;
	SuffixTrie * sTrie;
	pTrie = new PrefixTrie();
	sTrie = new SuffixTrie();

	// insert all the words
	// in both the tries
	for (int i = 0; i < words.size(); i++)
	{
		string str = words[i];
		pTrie->insert(str, i);
		sTrie->insert(str, i);
	}

	int ans = 0;

	//find the indices of the words with given prefix
	vector<int> prefixWords = pTrie->search(prefix);

	//find the indices of the words with given suffix
	vector<int> suffixWords = sTrie->search(suffix);

	// use two pointers to find
	// the common indices in both arrays

	int i = prefixWords.size() - 1;
	int j = suffixWords.size() - 1;

	while (i >= 0 && j >= 0)
	{
		if (prefixWords[i] == suffixWords[j])
			return prefixWords[i];
		if (prefixWords[i] > suffixWords[j])
			i--;
		else
			j--;
	}

	return -1;
}

import java.util.*;
import java.lang.*;
import java.io.*;

class Solution {
   public static int findWordsWithPrefAndSuff(List<String> words, String pref, String suff) {
        // your code goes here
        return -1;
    }
}

import java.util.*;
import java.lang.*;
import java.io.*;

// Definition of a TrieNode
class TrieNode
{
	// children array store pointer to TrieNode of next 26 alphabets
	TrieNode[] children = new TrieNode[26];
	// A flag used to identify the end of word nodes or leaf nodes
	boolean isEndOfWord;
	// A list to store the indices of the words
	// passing through the trie node 
	List<Integer> indices = new ArrayList < > ();
}

class PrefixTrie
{
	// Intialise the root of prefix trie
	TrieNode root = new TrieNode();

	void insert(String word, int index)
	{
		// point the current node as root
		TrieNode curr = root;
		for (int i = 0; i < word.length(); i++)
		{
			curr.indices.add(index);

			// add the index of the given word
			// to the indices array of current node
			int curInd = (int) word.charAt(i) - 'a';

			//create a new trie node
			// if child link is not found
			if (curr.children[curInd] == null)
			{
				curr.children[curInd] = new TrieNode();
			}

			curr = curr.children[curInd];
		}

		//set the value of isEndOfWord for last node
		// in the path
		curr.isEndOfWord = true;
		curr.indices.add(index);
	}

	List<Integer> search(String word)
	{
		// point the current node as root
		TrieNode curr = root;
		for (int i = 0; i < word.length(); i++)
		{
			// if child link is not found
			// it means prefix does not exists
			// return empty indices array
			int index = (int) word.charAt(i) - 'a';
			if (curr.children[index] == null)
			{
				return new ArrayList < > ();
			}

			curr = curr.children[index];
		}

		// if prefix is found completely
		// return indices associated with
		// last node in the path
		return curr.indices;
	}
}

// All operations performed in suffix trie
// are similar except the fact
// that strings are processed in reverse order
// both in insertion and searching
class SuffixTrie
{
	TrieNode root = new TrieNode();

	void insert(String word, int index)
	{
		TrieNode curr = root;
		for (int i = word.length() - 1; i >= 0; i--)
		{
			curr.indices.add(index);
			int curInd = (int) word.charAt(i) - 'a';
			if (curr.children[curInd] == null)
			{
				curr.children[curInd] = new TrieNode();
			}

			curr = curr.children[curInd];
		}

		curr.indices.add(index);
		curr.isEndOfWord = true;
	}

	List<Integer> search(String word)
	{
		TrieNode curr = root;
		for (int i = word.length() - 1; i >= 0; i--)
		{
			int index = (int) word.charAt(i) - 'a';
			if (curr.children[index] == null)
			{
				return new ArrayList < > ();
			}

			curr = curr.children[index];
		}

		return curr.indices;
	}
}

class Solution
{
	public static int findWordsWithPrefAndSuff(List<String> words, String prefix, String suffix)
	{
		// Intialise a prefix and a suffix trie seperately
		PrefixTrie pTrie = new PrefixTrie();
		SuffixTrie sTrie = new SuffixTrie();

		// insert all the words
		// in both the tries
		for (int i = 0; i < words.size(); i++)
		{
			String str = words.get(i);
			pTrie.insert(str, i);
			sTrie.insert(str, i);
		}

		int ans = 0;
		//find the indices of the words with given prefix
		List<Integer> prefixWords = pTrie.search(prefix);

		//find the indices of the words with given suffix
		List<Integer> suffixWords = sTrie.search(suffix);

		// use two pointers to find
		// the common indices in both arrays
		int i = prefixWords.size() - 1;
		int j = suffixWords.size() - 1;

		while (i >= 0 && j >= 0)
		{
			if (prefixWords.get(i) == suffixWords.get(j))
				return prefixWords.get(i);
			if (prefixWords.get(i) > suffixWords.get(j))
				i--;
			else
				j--;
		}

		return -1;
	}
}

Java

Solve a hard-level problem of finding words that start with a given prefix and end with a given suffix using tries. 

Prefix and Suffix Search

Solve a hard-level problem of finding words that start with a given prefix and end with a given suffix using tries.

Introduction to Tries

Prefix Search

Suffix Search

Bitwise Tries

Pattern Matching

File Systems

Trie Traversal

Search Engine

Miscellaneous

Conclusion

Prefix and Suffix Search