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

#include<iostream>
#include<vector>
using namespace std;

vector<vector<int>> findPalindromePairs(vector<string> words) {
    // your code goes here
    vector<vector<int>> answer;
    return answer;
}

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

// Definition of a trie node
class TrieNode
{
    public:

       	// an integer which stores the index of 
       	// thw word ending at current index
        int indexOfWordEndingHere = -1;

       	// children array store pointer to TrieNode of next 26 alphabets
        TrieNode *children[26];
    
       	// holds the indexes of all the words, whose later part of form a palindrome. 
        vector<int> palindromePrefixRemaining;
};

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

// checks if substring of word from index i till end of word 
// is a palindrome
bool hasPalindromeRemaining(string s, int i)
{
    int p1 = i;
    int p2 = s.size() - 1;
    while (p1 < p2)
    {
        if (s[p1] != s[p2])
            return false;
        p1++;
        p2--;
    }

    return true;
}

vector<vector < int>> findPalindromePairs(vector<string> words)
{
    Trie *trie = new Trie();
   	// Build the Trie
    for (int i = 0; i < words.size(); i++)
    {
        string word = words[i];

       	//point the current node to the root
        TrieNode *curr = trie->root;

       	// insert the reversord word into the trie
        reverse(word.begin(), word.end());
        string reversedWord = word;

        for (int j = 0; j < word.size(); j++)
        {
           	//check if substring from index to j till end of word 
           	// is a palindrome and insert it in array
            if (hasPalindromeRemaining(reversedWord, j))
            {
                curr->palindromePrefixRemaining.push_back(i);
            }

            char c = reversedWord[j] - 'a';
            if (!curr->children[c])
            {
                curr->children[c] = new TrieNode();
            }

            curr = curr->children[c];
        }

        curr->indexOfWordEndingHere = i;
    }

   	// Find pairs
    vector<vector < int>> pairs;

    for (int wordId = 0; wordId < words.size(); wordId++)
    {
        string word = words[wordId];

       	//point the current node to the root
        TrieNode *curr = trie->root;
        for (int j = 0; j < word.size(); j++)
        {
           	// Check for pairs of case 3.
            if (curr->indexOfWordEndingHere != -1 &&
                hasPalindromeRemaining(word, j))
            {
                pairs.push_back({ wordId, curr->indexOfWordEndingHere });
            }

           	// Move down to the next trie level.
            char c = word[j];
            curr = curr->children[c - 'a'];
            if (curr == nullptr)
                break;
        }

        if (curr == nullptr)
            continue;
       	// Check for pairs of case 1. Note the check to prevent non distinct pairs.
        if (curr->indexOfWordEndingHere != -1 && curr->indexOfWordEndingHere != wordId)
        {
            pairs.push_back({ wordId, curr->indexOfWordEndingHere });
        }

       	// Check for pairs of case 2.
        for (int otherIndex: curr->palindromePrefixRemaining)
        {
            pairs.push_back({ wordId, otherIndex });
        }
    }

    return pairs;
}

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

class Solution {
    
    static List<List<Integer>> findPalindromePairs(List<String> words){
        // your code goes here
        List<List<Integer>> answer = new ArrayList<>();
        return answer;
    }
}


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

// Definition of a trie node
class TrieNode
{
   	// an integer which stores the index of 
   	// thw word ending at current index
    int indexOfWordEndingHere = -1;

   	// children array store pointer to TrieNode of next 26 alphabets
    TrieNode[] children = new TrieNode[26];;

   	// holds the indexes of all the words, whose later part of form a palindrome. 
    List<Integer> palindromePrefixRemaining = new ArrayList<Integer> ();

}

class Trie
{
    TrieNode root = new TrieNode();
}

class Solution
{
   	// checks if substring of word from index i till end of word 
   	// is a palindrome
    static boolean hasPalindromeRemaining(String s, int i)
    {
        int p1 = i;
        int p2 = s.length() - 1;
        while (p1 < p2)
        {
            if (s.charAt(p1) != s.charAt(p2))
                return false;
            p1++;
            p2--;
        }

        return true;
    }

    static String reverseString(String s)
    {
        char str[] = s.toCharArray();
        int n = str.length;	// length of character array
        int start = 0, end = n - 1;
        while (start <= end)
        {
           	// Swapping the characters
            char temp = str[start];
            str[start] = str[end];
            str[end] = temp;
            start++;
            end--;
        }

       	//  Converting characterArray to String
        return String.valueOf(str);
    }

    static List<List < Integer>> findPalindromePairs(List<String> words)
    {
        Trie trie = new Trie();
       	// Build the Trie
        for (int wordId = 0; wordId < words.size(); wordId++)
        {
            String word = words.get(wordId);

           	//point the current node to the root
            TrieNode curr = trie.root;

           	// insert the reversord word into the trie
            String reversedWord = reverseString(word);

            for (int j = 0; j < word.length(); j++)
            {
               	//check if substring from index to j till end of word 
               	// is a palindrome and insert it in array
                if (hasPalindromeRemaining(reversedWord, j))
                {
                    curr.palindromePrefixRemaining.add(wordId);
                }

                int index = reversedWord.charAt(j) - 'a';
                if (curr.children[index] == null)
                {
                    curr.children[index] = new TrieNode();
                }

                curr = curr.children[index];
            }

            curr.indexOfWordEndingHere = wordId;
        }

       	// Find pairs
        List<List < Integer>> pairs = new ArrayList < > ();

        for (int wordId = 0; wordId < words.size(); wordId++)
        {
            String word = words.get(wordId);

           	//point the current node to the root
            TrieNode curr = trie.root;
            for (int j = 0; j < word.length(); j++)
            {
               	// Check for pairs of case 3.
                if (curr.indexOfWordEndingHere != -1 &&
                    hasPalindromeRemaining(word, j))
                {
                    pairs.add(Arrays.asList(wordId, curr.indexOfWordEndingHere));
                }

               	// Move down to the next trie level.
                char c = word.charAt(j);
                curr = curr.children[c - 'a'];
                if (curr == null)
                    break;
            }

            if (curr == null)
                continue;
           	// Check for pairs of case 1. Note the check to prevent non distinct pairs.
            if (curr.indexOfWordEndingHere != -1 && curr.indexOfWordEndingHere != wordId)
            {
                pairs.add(Arrays.asList(wordId, curr.indexOfWordEndingHere));
            }

           	// Check for pairs of case 2.
            for (int otherIndex: curr.palindromePrefixRemaining)
            {
                pairs.add(Arrays.asList(wordId, otherIndex));
            }
        }

        return pairs;
    }
}

Java

Solve a hard-level problem on finding palindrome pairs using tries. 

Palindromes Pairs

Solve a hard-level problem on finding palindrome pairs using tries.

Introduction to Tries

Prefix Search

Suffix Search

Bitwise Tries

Pattern Matching

File Systems

Trie Traversal

Search Engine

Miscellaneous

Conclusion

Palindromes Pairs

Problem statement

Example 1

Example 2

Example 3

Try it yourself

Intuition