Trie Data structure

Trie, also known as a prefix tree, is a tree-like data structure used for efficient retrieval of strings based on their prefixes. Following are key properties.

• Root Node: The starting point of the trie.
• Internal Nodes: Nodes that represent characters within a word.
• Leaf Nodes: Nodes that represent the end of a word.
• Edges: Connections between nodes that represent characters.

Example

Consider a trie containing the words “cat”, “dog”, and “car”.

         root
       / | \
      c  d  e
     / \  \  
    a  r*  o
   /        \
  t*         g*

We can represent it as below.

struct TrieNode {
        TrieNode* children[26] = {};
        bool isWord = false;
    };
struct Trie {
        TrieNode* root;
        Trie() { this->root = new TrieNode(); }
}

Can we use HashMap instead of trie?

Technically every Trie can be represented as prefix HashMap. Following is example of hash map for above example.

{
c: false
ca: false
cat: true
car: true
d: false
do: false
dog: true
}

Trie gives a better way to store these prefix and also it helps to run various algorithm on Trie data structure to solve many related problems.

Can we build trie non alphabets?

Yes. Trie data structure is not bound to alphabets characters only. It can be build for tree structure which represents the common prefix. Let’s take following as an example.

Here, o1 represents one of organization in a company. A customer can have more than one organization. Each organization can have multiple sites and each of those sites can have multiple cameras. Installation with one organization (o1), two sites (s1 and s2) and few cameras in those sites would look like the above.

We can also represent this structure using Trie as below.

struct TrieNode {
        unordered_map<string, TrieNode*> children = {};
        bool isStream = false;
    };
struct Trie {
        TrieNode* root;
        Trie() { this->root = new TrieNode(); }
}

Let’s go through various related problem to learn more about it.

208. Implement Trie (Prefix Tree)

https://leetcode.com/problems/implement-trie-prefix-tree/description/

Implement the Trie class:

• Trie() Initializes the trie object.
• void insert(String word) Inserts the string word into the trie.
• boolean search(String word) Returns true if the string word is in the trie (i.e., was inserted before), and false otherwise.
• boolean startsWith(String prefix) Returns true if there is a previously inserted string word that has the prefix prefix, and false otherwise.

Example 1:

Input
["Trie", "insert", "search", "search", "startsWith", "insert", "search"]
[[], ["apple"], ["apple"], ["app"], ["app"], ["app"], ["app"]]
Output
[null, null, true, false, true, null, true]

Following is code for reference.

class TrieNode {
    constructor(chr) {
        this.chr = chr;
        this.children = new Array(26).fill(null);
        this.isWord = false
    }
}
var Trie = function() {
    this.root = new TrieNode();
};

const charIndex = chr => chr.charCodeAt(0) - 'a'.charCodeAt(0);

/** 
 * @param {string} word
 * @return {void}
 */
Trie.prototype.insert = function(word) {
    let node = this.root;
    for (const chr of word) {
        const index = charIndex(chr);
        if(!node.children[index]) {
            node.children[index] = new TrieNode(chr);
        }
        node = node.children[index];
    }
    node.isWord = true;
};

/** 
 * @param {string} word
 * @return {boolean}
 */
Trie.prototype.search = function(word) {
    let node = this.root;
    for (const chr of word) {
        const index = charIndex(chr);
        if(!node.children[index]) {
            return false;
        }
        node = node.children[index];
    }
    return node.isWord;
};

/** 
 * @param {string} prefix
 * @return {boolean}
 */
Trie.prototype.startsWith = function(prefix) {
    let node = this.root;
    for (const chr of prefix) {
        const index = charIndex(chr);
        if(!node.children[index]) {
            return false;
        }
        node = node.children[index];
    }
    return true;   
};

14. Longest Common Prefix

https://leetcode.com/problems/longest-common-prefix/description

Write a function to find the longest common prefix string amongst an array of strings.

If there is no common prefix, return an empty string "".

Example 1:

Input: strs = ["flower","flow","flight"]
Output: "fl"

Approach# Use Trie

We can use build trie for the given words. Then find the longest common prefix such that each TrieNode will have count as count of words. Following is code for reference.

class Solution {
private:
    struct TrieNode {
        TrieNode* children[26] = {};
        int count = 0;
    };
    struct Trie {
        TrieNode* root;
        Trie() { this->root = new TrieNode(); }
        void addWord(string word) {
            int n = word.size();
            TrieNode* node = root;
            for (int i = 0; i < n; i++) {
                char chr = word[i];
                int index = chr - 'a';
                if (node->children[index] == nullptr) {
                    node->children[index] = new TrieNode();
                }
                node = node->children[index];
                node->count++;
            }
        }
        int search(TrieNode* node, int n) {
            for (TrieNode* child : node->children) {
                if (child != nullptr && child->count == n) {
                    return 1 + search(child, n);
                }
            }
            return 0;
        }
    };
    Trie* buildTrie(vector<string>& strs) {
        Trie* root = new Trie();
        for (string word : strs) {
            root->addWord(word);
        }
        return root;
    }

public:
    string longestCommonPrefix(vector<string>& strs) {
        int n = strs.size();
        Trie* trie = buildTrie(strs);
        int size = trie->search(trie->root, n);
        return strs[0].substr(0, size);
    }
};

1268. Search Suggestions System

https://leetcode.com/problems/search-suggestions-system/description/

You are given an array of strings products and a string searchWord.

Design a system that suggests at most three product names from products after each character of searchWord is typed. Suggested products should have common prefix with searchWord. If there are more than three products with a common prefix return the three lexicographically minimums products.

Return a list of lists of the suggested products after each character of searchWord is typed.

Example 1:

Input: products = ["mobile","mouse","moneypot","monitor","mousepad"], searchWord = "mouse"
Output: [["mobile","moneypot","monitor"],["mobile","moneypot","monitor"],["mouse","mousepad"],["mouse","mousepad"],["mouse","mousepad"]]

Approach

We can use Trie data structure to solve this problem as below.

1. Build Trie data structure for the given products list.
2. Build the list of all possible prefix for given searchWord i.e. [m,mo,mou,mous,mouse]
3. For each prefix from the searchWord , run a search on Trie.
4. Search on Trie will be done in two steps.

Step#1: First find the prefix in the Trie. If doesn’t exist then return empty list.

Step#2: If prefix found in Trie then the run the dfs(node) on subtree to find out all the words in the Trie subtree.

Following is code for reference.

class TrieNode {
    constructor(chr) {
        this.chr = chr;
        this.children = new Array(26).fill(null);
        this.isWord = false;
    }
}
class Trie {
    constructor() {
        this.root = new TrieNode();
    }
    getIndex(chr) {
        return chr.charCodeAt(0) - 'a'.charCodeAt(0);
    }
    add(word) {
        let node = this.root;
        for (const chr of word) {
            const index = this.getIndex(chr);
            if (!node.children[index]) {
                node.children[index] = new TrieNode(chr);
            }
            node = node.children[index];
        }
        node.isWord = true;
    }
    dfsWithPrefix(node, word, ans) {
        if (ans.length === 3) {
            return;
        }
        if (node.isWord) {
            ans.push(word.join(''));
        }
        for (const child of node.children) {
            if (child == null) {
                continue;
            }
            const chr = child.chr;
            word.push(chr);
            this.dfsWithPrefix(child, word, ans);
            word.pop(); // back track
        }
        return ans;
    }
    getWordsStartingWith(prefix) {
        let node = this.root;
        const ans = [];
        for (const chr of prefix) {
            const index = this.getIndex(chr);
            if (!node.children[index]) {
                return ans;
            }
            node = node.children[index];
        }
        // prefix exist in trie, now do dfs
        this.dfsWithPrefix(node, prefix.split(''), ans);
        return ans;
    }
}
/**
 * @param {string[]} products
 * @param {string} searchWord
 * @return {string[][]}
 */
var suggestedProducts = function (products, searchWord) {
    const trie = new Trie();
    for (const product of products) {
        trie.add(product);
    }
    // Build all the prefix
    const prefix = [];
    const result = [];
    for (const chr of searchWord) {
        prefix.push(chr);
        const local = trie.getWordsStartingWith(prefix.join(''));
        result.push(local);
    }
    return result;
};

79. Word Search

https://leetcode.com/problems/word-search/description/

Given an m x n grid of characters board and a string word, return true if word exists in the grid.

The word can be constructed from letters of sequentially adjacent cells, where adjacent cells are horizontally or vertically neighboring. The same letter cell may not be used more than once.

Example 1:

Input: board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "ABCCED"
Output: true

Approach

1. We don’t know the which cell to start the search, therefore we can simply try all cell which is same as first char of word.
2. For each starting cell, run dfs to find the match.

How to handle not revisiting the same cell again?

1. Use board and mark it empty ‘’ to on dfs start and restore it with original once dfs completes.
2. Use separate visited array of same size of board and mark it visited once dfs start and don’t launch if already marked visited.

To keep it simple, let’s go with #1 approach.

How to handle cell without any neighbors?

Generally we launch dfs for each neighbors and calculate answer based on that.

But in this problem, if there is no neighbors then we need to do the special check with current cell.

Therefore a special code block is added to handle this.

Follownig is code for the reference.

const getNeighbors = (board, i, j) => {
    const m = board.length;
    const n = board[0].length;
    const neighbors = [];
    const directions = [[-1, 0], [1, 0], [0, -1], [0, 1]]
    for (const [x, y] of directions) {
        const p = i + x;
        const q = j + y;
        if (p >= 0 && p < m && q < n && q >= 0) {
            neighbors.push([p, q]);
        }
    }
    return neighbors;
}
const dfs = (board, i, j, word, k) => {
    const m = board.length;
    const n = board[0].length;
    // base case: empty word
    if (k === word.length) {
        return true;
    }
    const cell = board[i][j];

    // return early if cell didn't match
    if (cell !== word[k]) {
        return false;
    }

    // mark as visisted
    board[i][j] = '';

    // Launch dfs for each neighbors
    const neighbors = getNeighbors(board, i, j);
    // Special check on no neighbors # simply match with the current cell and make sure length is exhasted
    if (neighbors.length === 0) {
        // Restore cell before return
        board[i][j] = cell;
        return cell === word[k] && k === word.length - 1;
    }
    for (const [p, q] of getNeighbors(board, i, j)) {
        if (dfs(board, p, q, word, k + 1)) {
            return true;
        }
    }

    // restore board
    board[i][j] = cell;
    return false;
}
/**
 * @param {character[][]} board
 * @param {string} word
 * @return {boolean}
 */
var exist = function (board, word) {
    if (!word) {
        return false;
    }
    const m = board.length;
    if (m === 0) {
        return false;
    }
    const n = board[0].length;
    for (let i = 0; i < m; i++) {
        for (let j = 0; j < n; j++) {
            const cell = board[i][j];
            if (cell === word[0]) {
                // Launch dfs
                if (dfs(board, i, j, word, 0)) {
                    return true;
                }
            }
        }
    }
    return false;
};

Time complexity

1. For the backtracking function, initially we could have at most 4 directions to explore, but further the choices are reduced into 3 (since we won’t go back to where we come from).
2. As a result, the execution trace after the first step could be visualized as a 3-nary tree, each of the branches represent a potential exploration in the corresponding direction.
3. Therefore, in the worst case, the total number of invocation would be the number of nodes in a full 3-nary tree, which is about 3^L.
4. We iterate through the board for backtracking, i.e. there could be N times invocation for the backtracking function in the worst case.
5. N is the number of cells in the board and L is the length of the word to be matched.

As a result, overall the time complexity of the algorithm would be O(N*3^L).

212. Word Search II

https://leetcode.com/problems/word-search-ii/description/

Given an m x n board of characters and a list of strings words, return all words on the board.

Each word must be constructed from letters of sequentially adjacent cells, where adjacent cells are horizontally or vertically neighboring. The same letter cell may not be used more than once in a word.

Example 1:

Input: board = [["o","a","a","n"],["e","t","a","e"],["i","h","k","r"],["i","f","l","v"]], words = ["oath","pea","eat","rain"]
Output: ["eat","oath"]

Approach #1: For each word, do the search as per previous problem and add into answer if exist otherwise ignore.

Time complexity of this would be O(M*N*3^L) where N is number of cells and M is number of words and L is avg size of each word.

This approach will lead to TLE.

Approach #2

Reason above approach throw TLE bcz we don’t leverage already processed steps. For example if we have two words mango and mandatae then we compute effort for common prefix man will be repeated.

Intuition here is to compute the common prefix only once.

One approach is to build Trie for the given words and then run the grid search as per Trie structure. What does it mean?

It means, similar to word-search #1 problem, where we were launch dfs for each cells on grid, we will also launch dfs for each cells on the grid, but for the root of the trie.

Here, the entire words list is now represented as single trie which is same as single word in the #1 problem.

This will help to process common prefix only once.

How to handle duplicate output?

We only don’t process the same cell again. It doesn’t mean we will not process the same trie branch again.

Therefore to avoid adding the same trie word node again, we will have to reset isWord=false on finding word.

Follownig is code for reference.

const getCharIndex = chr => chr.charCodeAt(0) - 'a'.charCodeAt(0);
const getNeighbors = (board, i, j) => {
    const m = board.length;
    const n = board[0].length;
    const neighbors = [];
    const directions = [[-1, 0], [1, 0], [0, -1], [0, 1]]
    for (const [x, y] of directions) {
        const p = i + x;
        const q = j + y;
        if (p >= 0 && p < m && q < n && q >= 0) {
            neighbors.push([p, q]);
        }
    }
    return neighbors;
}

const dfs = (board, trieNode, i, j, output) => {
    const m = board.length;
    const n = board[0].length;

    // skip if board is empty
    if(i ===m || j === n) {
        return;
    }

    const cell = board[i][j];
    const index = getCharIndex(cell);
    // if not found in trie then return early
    if (!trieNode.children[index]) {
        return;
    }
    const node = trieNode.children[index];
    // Add into output if found a word
    if (node.isWord) {
        output.push(node.word);
        // reset isWord flag to avoid choosing it again
       node.isWord = false; 
    }

    // marke as visited
    board[i][j] = '';

    // process neighbors
    for (const [p, q] of getNeighbors(board, i, j)) {
        // Process if it is not visited again, i.e. not marked as ''
        if (board[p][q]) {
            dfs(board, node, p, q, output);
        }
    }

    // restore cell
    board[i][j] = cell;
}
class TrieNode {
    constructor(chr) {
        this.chr = chr;
        this.children = new Array(26).fill(null);
        this.isWord = false;
        this.word = null;
    }
}
class Trie{
    constructor() {
        this.root = new TrieNode();
    }
    add(word) {
        let node = this.root;
        for (const chr of word) {
            const index = getCharIndex(chr);
            if(!node.children[index]) {
                node.children[index] = new TrieNode(chr);
            }
            node = node.children[index];
        }
        node.isWord = true;
        node.word = word;
    }
}
const buildTrie = words => {
    const trie = new Trie();
    for (const word of words) {
        trie.add(word);
    }
    return trie;
}
/**
 * @param {character[][]} board
 * @param {string[]} words
 * @return {string[]}
 */
var findWords = function (board, words) {
    const trie = buildTrie(words);
    const m = board.length;
    const n = board[0].length;
    const output = [];
    for (let i = 0; i < m; i++) {
        for (let j = 0; j < n; j++) {
            dfs(board, trie.root, i, j, output);
        }
    }
    return output;
};

421. Maximum XOR of Two Numbers in an Array

https://leetcode.com/problems/maximum-xor-of-two-numbers-in-an-array/description/

Given an integer array nums, return the maximum result of nums[i] XOR nums[j], where 0 <= i <= j < n.

Example 1:

Input: nums = [3,10,5,25,2,8]
Output: 28
Explanation: The maximum result is 5 XOR 25 = 28.

Approach # For every pair, find out the XOR and track the max

1. This approach find XOR for each pair and calculate the global max.
2. Time complexity will be O(n*n) therefore not a suitable approach.

Approach #2: Build Trie for given numbers and find out the opposite branch to get maximum XOR

1. For given Aand B, we can maximize the A XOR B if digit on each position in binary representation is opposite.
2. In the Approach#1, we blindly perform XOR on each pair therefore result into TLE.
3. To find out the XOR pair, we can build Trie for given numbers and search the opposite branch.
4. Since number of digits in the binary representation could be different therefore pad the extra zeros to match the digits count.
5. When search for opposite branch, if not found then return same as XOR for two same number is zero.

Following is code for reference.

class TrieNode{
    constructor(chr) {
        this.chr = chr;
        this.children = new Array(2).fill(null);
        this.isWord = false;
        this.word = null;
    }
}
class Trie {
    constructor() {
        this.root = new TrieNode();
    }
    getIndex(chr) {
        return chr === '0' ? 0: 1;
    }
    getOpposite(chr) {
        return chr ==='0' ? '1': '0';
    }
    add(word) {
        let node = this.root; 
        for (const chr of word) {
            const index = this.getIndex(chr);
            if(!node.children[index]){
                node.children[index] = new TrieNode(chr);
            }
            node = node.children[index];
        }
        node.isWord = true;
        node.word = word;
    }
    search(word) {
        let node = this.root;
        for (const chr of word){
            const index = this.getIndex(chr);
            // get opposit chr
            const oppositChr = this.getOpposite(chr);
            const oppositIndex = this.getIndex(oppositChr);
            
            // if exist then use the opposit path
            if(node.children[oppositIndex]) {
                node = node.children[oppositIndex];
            } else {
                // if doesn't exist then follow word path
                node = node.children[index];
            }
        }
        // at the end, word search will complete
        const num1 = Number.parseInt(word, 2);
        const num2 = Number.parseInt(node.word, 2);
        return num1 ^ num2;
    }
}
/**
 * @param {number[]} nums
 * @return {number}
 */
var findMaximumXOR = function(nums) {
    const binaryArr = nums.map(n => n.toString(2));
    let maxLength = 0;
    for (const bin of binaryArr) {
        maxLength = Math.max(maxLength, bin.length);
    }
    // Pad extra 0 to each binary string
    const arr = binaryArr.map(a => {
        const diff = maxLength - a.length;
        const pad = [];
        for (let i=0; i < diff; i++) {
            pad.push('0');
        }
        return pad.join('') + a;
    });
    
    // Build trie
    const trie = new Trie();
    for (const word of arr) {
        trie.add(word);
    }
    let ans = 0;
    // for each word, predict the max opposite
    for (const word of arr) {
        const result = trie.search(word);
        ans = Math.max(ans, result);
    }
    return ans;
};

648. Replace Words

In English, we have a concept called root, which can be followed by some other word to form another longer word — let’s call this word derivative. For example, when the root "help" is followed by the word "ful", we can form a derivative "helpful".

Given a dictionary consisting of many roots and a sentence consisting of words separated by spaces, replace all the derivatives in the sentence with the root forming it. If a derivative can be replaced by more than one root, replace it with the root that has the shortest length.

Return the sentence after the replacement.

Example 1:

Input: dictionary = ["cat","bat","rat"], sentence = "the cattle was rattled by the battery"
Output: "the cat was rat by the bat"

Approach

1. We can build Trie for given dictionary words.
2. For each word in the sentence, we will search in the Trie. If found then use it to replace otherwise not.

Following is code for reference.

class TrieNode {
    constructor(chr) {
        this.chr = chr;
        this.children = new Array(26).fill(null);
        this.isWord = false;
        this.word = "";
    }
}
class Trie {
    constructor() {
        this.root = new TrieNode();
    }
    getIndex(chr) {
        return chr.charCodeAt(0) - 'a'.charCodeAt(0);
    }
    insert(word) {
        let node = this.root;
        for (const chr of word) {
            const index = this.getIndex(chr);
            if (!node.children[index]) {
                node.children[index] = new TrieNode(chr);
            }
            node = node.children[index]
        }
        node.isWord = true;
        node.word = word;
    }
    search(word) {
        let node = this.root;
        for (const chr of word) {
            if (node.isWord) {
                return node.word;
            }
            const index = this.getIndex(chr);
            if (!node.children[index]) {
                return null;
            }
            node = node.children[index];
        }
        return null;
    }
}
const buildTrie = words => {
    const trie = new Trie();
    for (const word of words) {
        trie.insert(word);
    }
    return trie;
}
/**
 * @param {string[]} dictionary
 * @param {string} sentence
 * @return {string}
 */
var replaceWords = function (dictionary, sentence) {
    const trie = buildTrie(dictionary);
    const words = sentence.split(" ");
    const output = words.map(word => {
        const match = trie.search(word);
        if (match) {
            return match;
        }
        return word;
    });
    return output.join(" ");
};

1065. Index Pairs of a String

https://leetcode.com/problems/index-pairs-of-a-string/description/

Given a string text and an array of strings words, return an array of all index pairs [i, j] so that the substring text[i...j] is in words.

Return the pairs [i, j] in sorted order (i.e., sort them by their first coordinate, and in case of ties sort them by their second coordinate).

Example 1:

Input: text = "thestoryofleetcodeandme", words = ["story","fleet","leetcode"]
Output: [[3,7],[9,13],[10,17]]

Approach # 1: Brute force

1. Build hash map for words for quick lookup.
2. Build each possible substring of text , check if it exist in map. If does then use it as an answer.

Time complexity

1. m denote text.length
2. n denote words.length
3. s as the average length of the words

Following is the code for reference.

/**
 * @param {string} text
 * @param {string[]} words
 * @return {number[][]}
 */
var indexPairs = function (text, words) {
    const ans = [];
    const n = text.length;
    const set = new Set(words);
    for (let i = 0; i < n; i++) {
        for (let j = i; j < n; j++) {
            const candidate = text.substring(i, j + 1);
            if (set.has(candidate)) {
                ans.push([i, j]);
            }
        }
    }
    return ans;
};

Time complexity: O(n⋅s+m^3)

Approach #2: Using Trie

Consider an example with text = "abacaba". In the previous approach, at some point, we check the substring text[1...4] = "baca" and then the substring text[1...5] = "bacab". However, we do not use any information on "baca" while checking "bacab".

With a trie, we can check the substring faster using the information about its prefix.

We will use one more important property of a trie:

1. If a string belongs to a trie, all its prefixes also belong to it.
2. For example, if there is a node corresponding to "bacab", there must also be nodes corresponding to "baca", "bac", "ba", and "b".
3. There exists an edge labeled with the letter "b" from the node "baca" to the node "bacab".
4. Let’s say we have already considered the substring text[i...j] and know what node in the trie corresponds to it. Now we want to add text[j+1] to the substring and proceed to text[i...j+1]. If there exists an edge labeled with text[j+1] outgoing from the current node, we traverse this edge and come to the node corresponding to text[i...j+1]. Otherwise, this substring is not in the trie, and we can stop checking the substrings starting at the i-th element.

Algorithm

1. Maintain the trie. Insert all elements from words into it. Each trie node contains (possibly zero) outgoing edges to other nodes and a flag that indicates whether the string corresponding to the node belongs to the words set (whether it is marked).
2. Iterate i from 0 to text.length-1.

• Let p be the trie node corresponding to the current substring, which is empty now. p is the trie root initially.
• Iterate j from i to text.length-1
• If an outgoing edge from p labeled with text[j] does not exist, we cannot add characters to the current substring anymore, so break from the loop. Otherwise, traverse this edge and set p to its child. If the node is marked, it means text[i...j] belongs to the set of words, so add the pair [i, j] to the answer.
• Note: this optimization is what makes this approach much more efficient because we break from the loop once we know there cannot be any more answers.

3. Return the answer.

Following is code for reference.

class TrieNode {
    constructor(chr) {
        this.children = new Array(26).fill(null);
        this.chr = chr;
        this.isWord = false;
    }
}
class Trie {
    constructor() {
        this.root = new TrieNode();
    }
    getIndex(chr) {
        return chr.charCodeAt(0) - 'a'.charCodeAt(0);
    }
    insert(word) {
        if (!word) {
            return;
        }
        let node = this.root;
        for (const chr of word) {
            const index = this.getIndex(chr);
            if (!node.children[index]) {
                node.children[index] = new TrieNode(chr);
            }
            node = node.children[index];
        }
        node.isWord = true;
    }
}
const buildTrie = words => {
    const trie = new Trie();
    // insert each words into trie    
    for (const word of words) {
        trie.insert(word);
    }
    return trie;
}

/**
 * @param {string} text
 * @param {string[]} words
 * @return {number[][]}
 */
var indexPairs = function (text, words) {
    const trie = buildTrie(words);
    const ans = [];
    const n = text.length;
    for (let i = 0; i < n; i++) {
        let node = trie.root;
        for (let j = i; j < n; j++) {
            const chr = text[j];
            const index = trie.getIndex(chr);
            if (!node.children[index]) {
                break;
            }
            node = node.children[index];
            if (node.isWord) {
                ans.push([i, j]);
            }
        }
    }
    return ans;
};

Time complexity: O(n⋅s+m^2).

720. Longest Word in Dictionary

https://leetcode.com/problems/longest-word-in-dictionary/description/

Given an array of strings words representing an English Dictionary, return the longest word in words that can be built one character at a time by other words in words.

If there is more than one possible answer, return the longest word with the smallest lexicographical order. If there is no answer, return the empty string.

Note that the word should be built from left to right with each additional character being added to the end of a previous word.

Example 1:

Input: words = ["w","wo","wor","worl","world"]
Output: "world"
Explanation: The word "world" can be built one character at a time by "w", "wo", "wor", and "worl".

Example 2:

Input: words = ["a","banana","app","appl","ap","apply","apple"]
Output: "apple"
Explanation: Both "apply" and "apple" can be built from other words in the dictionary. However, "apple" is lexicographically smaller than "apply".

Approach

1. build trie for all nodes with isWord as flag.
2. Run bfs on trie as a general tree.
3. Every node; only use other children as neighbors if it has isWord==true .
4. Run the level order traversal and choose first ans at i=0 to choose the lexicographical order.

Following is code for reference.

class TrieNode {
    constructor(chr) {
        this.chr = chr;
        this.children = new Array(26).fill(null);
        this.isWord = false;
        this.word = "";
    }
}
class Trie {
    constructor() {
        this.root = new TrieNode();
    }
    getIndex(chr) {
        return chr.charCodeAt(0) - 'a'.charCodeAt(0);
    }
    insert(word) {
        let node = this.root;
        for (const chr of word) {
            const index = this.getIndex(chr);
            if (!node.children[index]) {
                node.children[index] = new TrieNode(chr);
            }
            node = node.children[index]
        }
        node.isWord = true;
        node.word = word;
    }
}
const buildTrie = words => {
    const trie = new Trie();
    for (const word of words) {
        trie.insert(word);
    }
    return trie;
}
const getNeighbors = node => {
    const neighbors = [];
    for (const t of node.children) {
        if (t && t.isWord) {
            neighbors.push(t);
        }
    }
    return neighbors;
}
/**
 * @param {string[]} words
 * @return {string}
 */
var longestWord = function (words) {
    const trie = buildTrie(words);
    const queue = [trie.root];
    let ans = null;
    while (queue.length > 0) {
        const n = queue.length;
        for (let i = 0; i < n; i++) {
            const node = queue.shift();
            // Choose first as ans to satisfy lexicographical sorting order
            if (i == 0) {
                ans = node;
            }
            for (const neighbor of getNeighbors(node)) {
                queue.push(neighbor);
            }
        }
    }
    return ans.word;
};

1023. Camelcase Matching

https://leetcode.com/problems/camelcase-matching/description/

Given an array of strings queries and a string pattern, return a boolean array answer where answer[i] is true if queries[i] matches pattern, and false otherwise.

A query word queries[i] matches pattern if you can insert lowercase English letters pattern so that it equals the query. You may insert each character at any position and you may not insert any characters.

Example 1:

Input: queries = ["FooBar","FooBarTest","FootBall","FrameBuffer","ForceFeedBack"], pattern = "FB"
Output: [true,false,true,true,false]
Explanation: "FooBar" can be generated like this "F" + "oo" + "B" + "ar".
"FootBall" can be generated like this "F" + "oot" + "B" + "all".
"FrameBuffer" can be generated like this "F" + "rame" + "B" + "uffer".

Approach

We can build trie for each queries with 52 node, 26 for smallcase letter and 26 for uppercase letter.

We can then do the pattern search dfs() algo as below.

1. Neighbor of nodes will be all the lowercase nodes as well as the matching upper case node.
2. To run the recursive dfs() on neighbor, we need to check if need to advance pattern char or not. We will only advance if node is upper case and matching with pattern char.
3. Every time dfs reach to word node and pattern is also exhausted then add word into Set<word>

Use this Set<word> as lookup to check if query match the pattern or not.

Following is code for reference.

class TrieNode {
    constructor(chr) {
        this.chr = chr;
        this.children = new Array(52).fill(null);
        this.isWord = false;
        this.word = null;
    }
}
class Trie {
    constructor() {
        this.root = new TrieNode();
    }
    getIndex(chr) {
        if (isLowerCase(chr)) {
            return chr.charCodeAt(0) - 'a'.charCodeAt(0);
        }
        const lower = chr.toLowerCase();
        return 26 + lower.charCodeAt(0) - 'a'.charCodeAt(0);
    }
    add(word) {
        let node = this.root;
        for (const chr of word) {
            const index = this.getIndex(chr);
            if (!node.children[index]) {
                node.children[index] = new TrieNode(chr);
            }
            node = node.children[index];
        }
        node.isWord = true;
        node.word = word;
    }
}
const buildTrie = queries => {
    const trie = new Trie();
    for (const query of queries) {
        trie.add(query);
    }
    return trie;
}
const isLowerCase = chr => chr.toLowerCase() === chr;
const getNeighbors = (node, pChar) => {
    return node.children.filter(child => {
        // if null then exclude
        if (!child) {
            return false;
        }
        // if upper case then must match
        if (!isLowerCase(child.chr)) {
            return child.chr === pChar;
        }
        // If lower case then it's ok if doesn't match
        return true;
    });
}
const getNextPatternIndex = (qChr, pChr, i) => {
    // if both are matching then move
    if(qChr === pChr) {
        return i + 1;
    }
    // if query is lowercase then we can insert into pattern i.e. no need to move
    if(isLowerCase(qChr)) {
        return i;
    }
    // if query is upper case then both must has to match therefore need to move
    return i + 1;
}
const dfs = (node, pattern, i, set) => {
    // base case
    if (!node) {
        return;
    }

    // word and pattern is exhausted
    if (node.isWord && i === pattern.length) {
        set.add(node.word);
    }
    // process neighbors
    const chr = pattern[i];
    const neighbors = getNeighbors(node, chr);
    for (const neighbor of neighbors) {
        // Decide if need to increment pattern index or not
        const nextPatternIndex = getNextPatternIndex(neighbor.chr, chr, i);
        dfs(neighbor, pattern, nextPatternIndex, set)
    }
}
/**
 * @param {string[]} queries
 * @param {string} pattern
 * @return {boolean[]}
 */
var camelMatch = function (queries, pattern) {
    const trie = buildTrie(queries);
    const set = new Set();
    dfs(trie.root, pattern, 0, set);
    return queries.map(query => set.has(query));
};

676. Implement Magic Dictionary

Design a data structure that is initialized with a list of different words. Provided a string, you should determine if you can change exactly one character in this string to match any word in the data structure.

Implement the MagicDictionary class:

• MagicDictionary() Initializes the object.
• void buildDict(String[] dictionary) Sets the data structure with an array of distinct strings dictionary.
• bool search(String searchWord) Returns true if you can change exactly one character in searchWord to match any string in the data structure, otherwise returns false.

Example 1:

Input
["MagicDictionary", "buildDict", "search", "search", "search", "search"]
[[], [["hello", "leetcode"]], ["hello"], ["hhllo"], ["hell"], ["leetcoded"]]
Output
[null, null, false, true, false, false]

Explanation
MagicDictionary magicDictionary = new MagicDictionary();
magicDictionary.buildDict(["hello", "leetcode"]);
magicDictionary.search("hello"); // return False
magicDictionary.search("hhllo"); // We can change the second 'h' to 'e' to match "hello" so we return True
magicDictionary.search("hell"); // return False
magicDictionary.search("leetcoded"); // return False

Approach

1. Build Trie for given dictionary words.
2. In search() we need to skip exactly one char.
3. It means we can start with skip=1
4. We have two choices with each node
5. Choice 1: Do not skip for matched node
6. Choice 2: If skip > 0 then we have choice to skip match char for all neighbors and record the result
7. Return result from these two choices.

Following is code for reference.

const getIndex = chr => chr.charCodeAt(0) - 'a'.charCodeAt();
class TrieNode {
    constructor(chr) {
        this.chr = chr;
        this.children = new Array(26).fill(0);
        this.isWord = false;
    }
}
class Trie {
    constructor() {
        this.root = new TrieNode();
    }
    insert(word) {
        if(!word) {
            return;
        }
        let currentNode = this.root;
        for (const chr of word) {
            const index = getIndex(chr);
            if(!currentNode.children[index]) {
                currentNode.children[index]  = new TrieNode(chr);
            }
            currentNode = currentNode.children[index];
        }
        currentNode.isWord = true;
    }
    search(word, skip, i, currentNode) { 

        if(!currentNode) {
            return false;
        }
        // base case
        if(i === word.length) {
            if(currentNode && currentNode.isWord && skip === 0) {
                return true;
            }
            return false;
        }
        const chr = word[i];
        const index = getIndex(chr);
        let doNotSkip = false;
        if(currentNode.children[index]) {
           doNotSkip = this.search(word, skip, i+1, currentNode.children[index]); 
        } 
        let found = false;
        
        // skip as per limit
        if(skip > 0) {
           const neighbors = [];
            for (const node of currentNode.children) {
                if(node && node.chr !== chr) {
                  neighbors.push(node);  
                }
            }
           for (const neighbor of neighbors) {
              found = found ||  this.search(word, skip - 1, i+1, neighbor);
           } 
        }  
        return found || doNotSkip;
    }
}
/**
 * Initialize your data structure here.
 */
var MagicDictionary = function() {
    this.trie = new Trie();
};

/**
 * Build a dictionary through a list of words 
 * @param {string[]} dict
 * @return {void}
 */
MagicDictionary.prototype.buildDict = function(dict) {
    for (const word of dict) {
        this.trie.insert(word);
    }
};

/**
 * Returns if there is any word in the trie that equals to the given word after modifying exactly one character 
 * @param {string} word
 * @return {boolean}
 */
MagicDictionary.prototype.search = function(word) {
   return this.trie.search(word, 1, 0, this.trie.root); 
};

1178. Number of Valid Words for Each Puzzle

With respect to a given puzzle string, a word is valid if both the following conditions are satisfied:

• word contains the first letter of puzzle.
• For each letter in word, that letter is in puzzle.
• For example, if the puzzle is "abcdefg", then valid words are "faced", "cabbage", and "baggage", while
• invalid words are "beefed" (does not include 'a') and "based" (includes 's' which is not in the puzzle).

Return an array answer, where answer[i] is the number of words in the given word list words that is valid with respect to the puzzle puzzles[i].

Example 1:

Input: 
words = ["aaaa","asas","able","ability","actt","actor","access"], 
puzzles = ["aboveyz","abrodyz","abslute","absoryz","actresz","gaswxyz"]
Output: [1,1,3,2,4,0]
Explanation: 
1 valid word for "aboveyz" : "aaaa" 
1 valid word for "abrodyz" : "aaaa"
3 valid words for "abslute" : "aaaa", "asas", "able"
2 valid words for "absoryz" : "aaaa", "asas"
4 valid words for "actresz" : "aaaa", "asas", "actt", "access"
There are no valid words for "gaswxyz" cause none of the words in the list contains letter 'g'.

Approach 1: Hashing (Bitmask)

1. We have lots of puzzles to answer.
2. To handle a multi-query problem, such as this one, it is beneficial to select a data structure that allows us to efficiently address each query.
3. As per constraints (1 <= puzzles.length <= 10⁴ puzzles[i].length == 7) we have many words and puzzles, but the length of each word and each puzzle is short.
4. A constraint under 10 usually accepts a method with N! time complexity with respect to this constraint.
5. Instead of picking one puzzle and matching with one word at a time, can we do in bin?
6. I.e. group similar words into a bin and only compare bin with puzzle.

There are two common ways to group strings into “bins”:

1. Trie
2. Set (hashing)

Let’s try #2 with this approach.

The next problem is what kinds of words we want to put together?

One of the condition is that every chars in puzzle should exist in word. It means, we can put words that contain the same letters into the same bin.

Can we use Set as a hashmap key?

Instead of using Set , since our chars are only lowercase letters therefore we can use binary number with 26 digits to represent it as below.

This is called Bitmasking.

Following is code for this approach.

const getIndex = chr => chr.charCodeAt(0) - 'a'.charCodeAt(0);
const getHash = word => {
    let mask = 0;
    for (const chr of word) {
        const index = getIndex(chr);
        const pad = 1 << index;
        mask |= pad;            
    }  
    return mask;
}
const usingBitsManipulations = (words, puzzles) => {
    // build frequency of encoded word
    const wordsFrequency = new Map();
    for (const word of words) {
        const mask = getHash(word);
        wordsFrequency.set(mask, !wordsFrequency.has(mask) ? 1: wordsFrequency.get(mask) + 1);
        
    }
    
    const result = [];

    // process each puzzle
    for (const puzzle of puzzles) {
        const mask = getHash(puzzle);
        let sub = mask;
        let count = 0;
        const first = 1 << getIndex(puzzle[0]);
        while(true) {

            // if fist char match and word exist
            if((sub & first) && wordsFrequency.has(sub) ) {
                count += wordsFrequency.get(sub);
            }
            if(sub === 0) {
                break;
            }
            sub = (sub - 1) & mask; // get the next substring            
        }
        result.push(count);
        
    }
    
    return result;
}
/**
 * @param {string[]} words
 * @param {string[]} puzzles
 * @return {number[]}
 */
var findNumOfValidWords = function(words, puzzles) {
   return usingBitsManipulations(words, puzzles);
};

Approach #2: Using Trie

A trie can help us to quickly determine whether a word exists among all the words. Thus, it is similar to a dictionary.

However, if we want to put all the words into a trie, then in the worst case, none of the words start with the same letter, and thus every character of every word has its own node in the trie.

As determined in Approach 1, the validity of a word only depends on the letters in the word. So first, we can remove the duplicate letters from each word.

In this way, the maximum length of a word becomes 26 instead of N

Moreover, we can sort the letters in word in ascending order to further aggregate the same letters together, because sorted words are more likely to share a common prefix than unsorted words.

Also, we know that the length of puzzle is 7, and a valid word must consist entirely of letters in puzzle.
Therefore, any words containing more than 7 distinct letters are always invalid.

That is to say, our trie is at most 7 levels deep.

In conclusion, the maximum number of nodes in the trie is 7!=5040, which is small enough to iterate over for each puzzle.

As before, we must search for all valid words for each puzzle. However, instead of checking every subset of the puzzle, we can now perform a simple tree iteration using DFS. We can traverse the tree following the nodes inside the sorted set of puzzle, and when we meet a word and have already seen the first letter in puzzle, then the word must be valid.

Algorithm

Step 1: Build the trie.

• For each word in words:
• Sort the word and remove duplicate letters.
• Store the word, which is now a sorted list of distinct characters, in the trie.

Step 2: Count the number of valid words for each puzzle.

• For each puzzle in puzzles:
• Iterate over the trie to find all valid words for the current puzzle.

Following is code for reference.

class TrieNode {
    constructor(chr) {
        this.chr = chr;
        this.children = new Array(26).fill(null);
        this.isWord = false;
        this.count = 0;
    }
}
class Trie {
    constructor() {
        this.root = new TrieNode();
    }
    getIndex(chr) {
        return chr.charCodeAt(0) - 'a'.charCodeAt(0);
    }
    insert(word) {
        let node = this.root;
        for (const chr of word) {
            const index = this.getIndex(chr);
            if (!node.children[index]) {
                node.children[index] = new TrieNode(chr);
            }
            node = node.children[index]
        }
        node.isWord = true;
        node.count++;
    }
    dfs(set, node, firstChr, isFirstWordMatched) {
        // if node is word then count it
        let count = 0;
        if (node.isWord && isFirstWordMatched) {
            count += node.count;
        }
        // Get neighbors
        const neighbors = node.children.filter(child => child && set.has(child.chr));

        for (const neighbor of neighbors) {
            // If matced with first word of puzzle then set the flag
            const value = isFirstWordMatched || neighbor.chr === firstChr;
            count += this.dfs(set, neighbor, firstChr, value);
        }
        return count;
    }
}
const buildTrie = words => {
    const trie = new Trie();
    for (const word of words) {
        // Skip processed word with > 7 len
        if (word.length > 7) {
            continue;
        }
        trie.insert(word);
    }
    return trie;
}

/**
 * @param {string[]} words
 * @param {string[]} puzzles
 * @return {number[]}
 */
var findNumOfValidWords = function (words, puzzles) {
    const processed = words.map(word => {
        // Remove duplicte chrs in word
        const set = new Set(word.split(''));
        const output = Array.from(set);
        output.sort();
        return output.join('');
    });
    const trie = buildTrie(processed);
    // Search each pattern in the Trie
    return puzzles.map(puzzle => {
        const set = new Set(puzzle.split(''));
        return trie.dfs(set, trie.root, puzzle[0], false);
    })
};

745. Prefix and Suffix Search

https://leetcode.com/problems/prefix-and-suffix-search/description

Design a special dictionary that searches the words in it by a prefix and a suffix.

Implement the WordFilter class:

• WordFilter(string[] words) Initializes the object with the words in the dictionary.
• f(string pref, string suff) Returns the index of the word in the dictionary, which has the prefix pref and the suffix suff. If there is more than one valid index, return the largest of them. If there is no such word in the dictionary, return -1.

Example 1:

Input
["WordFilter", "f"]
[[["apple"]], ["a", "e"]]
Output
[null, 0]

Approach #1: Two Tries + Set Intersection [Time Limit Exceeded]

1. Build prefixTrie trie using all the words with the index for every prefix.
2. Build second reverseTrie for reversed word with the index of every suffix.
3. Search prefix in prefixTrie and search reverse of suffix in the reverseTrie .
4. Return the common indexes.

Following is code for reference.

class TrieNode {
    constructor(chr) {
        this.chr = chr;
        this.children = new Array(26).fill(null);
        this.indexes = new Set();
    }
}
class Trie {
    constructor() {
        this.root = new TrieNode();
    }
    getIndex(chr) {
        return chr.charCodeAt(0) - 'a'.charCodeAt(0);
    }
    add(word, i) {
        let node = this.root;
        for (const chr of word) {
            const index = this.getIndex(chr);
            if (!node.children[index]) {
                node.children[index] = new TrieNode(chr);
            }
            node = node.children[index];
            node.indexes.add(i);
        }
    }
    search(word) {
        let node = this.root;
        for (const chr of word) {
            const index = this.getIndex(chr);
            if (!node.children[index]) {
                return new Set();
            }
            node = node.children[index];
        }
        return node.indexes;
    }
}
/**
 * @param {string[]} words
 */
var WordFilter = function (words) {
    // Build prefix trie
    const prefixTrie = new Trie();
    for (let i = 0; i < words.length; i++) {
        prefixTrie.add(words[i], i);
    }
    // Build reverse trie
    const reverseTrie = new Trie();
    for (let i = 0; i < words.length; i++) {
        const word = words[i];
        const reverse = word.split('').reverse().join('');
        reverseTrie.add(reverse, i);
    }
    this.prefixTrie = prefixTrie;
    this.reverseTrie = reverseTrie;
};

/** 
 * @param {string} pref 
 * @param {string} suff
 * @return {number}
 */
WordFilter.prototype.f = function (pref, suff) {
    const left = this.prefixTrie.search(pref);
    const reverse = suff.split('').reverse().join('');
    const right = this.reverseTrie.search(reverse);
    let ans = -1;
    for (const key of left) {
        if (key > ans && right.has(key)) {
            ans = key;
        }
    }
    return ans;
};

/** 
 * Your WordFilter object will be instantiated and called as such:
 * var obj = new WordFilter(words)
 * var param_1 = obj.f(pref,suff)
 */

Approach #3: Trie of Suffix Wrapped Words [Accepted]

Instead of searching prefix and suffix separately, what if we can design a single trie and do the single search?

We can take following approach.

1. We can search for suffix#prefix .
2. It means, we can build a trie with all possible suffix with concatenating actual word.

Following is code reference.

class TrieNode {
    constructor(chr) {
        this.chr = chr;
        this.children = new Array(27).fill(null);
        this.index = -1;
    }
}
class Trie {
    constructor() {
        this.root = new TrieNode();
    }
    getIndex(chr) {
        if (chr === '#') {
            return 26;
        }
        return chr.charCodeAt(0) - 'a'.charCodeAt(0);
    }
    add(word, i) {
        let node = this.root;
        for (const chr of word) {
            const index = this.getIndex(chr);
            if (!node.children[index]) {
                node.children[index] = new TrieNode(chr);
            }
            node = node.children[index];
            node.index = i;
        }
    }
    search(word) {
        let node = this.root;
        for (const chr of word) {
            const index = this.getIndex(chr);
            if (!node.children[index]) {
                return -1;
            }
            node = node.children[index];
        }
        return node.index;
    }
}
/**
 * @param {string[]} words
 */
var WordFilter = function (words) {
    const trie = new Trie();
    for (let i = 0; i < words.length; i++) {
        const word = words[i];
        for (let j = word.length; j >= 0; j--) {
            const suffix = word.substring(j);
            const token = `${suffix}#${word}`;
            trie.add(token, i);
        }
    }
    this.trie = trie;
};

/** 
 * @param {string} pref 
 * @param {string} suff
 * @return {number}
 */
WordFilter.prototype.f = function (pref, suff) {
    const token = `${suff}#${pref}`;
    return this.trie.search(token);
};

Group alerts generated by Camera

Under Google command and control system, the cameras are installed in a hierarchy. At the top is an organization. A customer can have more than one organization. Each organization can have multiple sites and each of those sites can have multiple cameras. Installation with one organization (o1), two sites (s1 and s2) and few cameras in those sites would look like the following.

We have a fault detection system that can generate a stream of alarms if a fault is detected. The fault can occur at any level (ex: Single camera was tampered, a central network switch failure affecting an entire site). To reduce the noise, our goal is to consume this stream and surface faults at top of the hierarchy. Please write a function that takes a stream of such alerts as an array and returns an array after removing all alerts which can be rolled up at a higher level. The alerts in the input do not come in any specific order.

Example:

Input: ["/o1/s1/c1", "/o1/s1/c2", "/o1/s2/c2", "/o1/s1"]
Output: ["/o1/s1", "/o1/s2/c2"]

Input: ["/o1", "/o1/s1", "/o1/s2"]
Output: ["/o1"]

Input: ["/o1/s1/c1", "/o1/s1/c12", "/o1/s1/c3"]
Output: "/o1/s1/c1", "/o1/s1/c12", "/o1/s1/c3"]

Approach#1: Use trie and dfs search

We can build a dynamic Trie followed by searching the first stream found in the path and include it as an answer.

Following is code for reference.

#include <bits/stdc++.h>
using namespace std;
vector<string> split(string str) {
    stringstream ss(str);
    string token;
    vector<string> ans;
    while(getline(ss, token, '/')) {
        ans.push_back(token);
    }
    return ans;
}
struct TrieNode{
    unordered_map<string, TrieNode*> children = {};
    bool isAlert = false;
    string key;
    string alert;
    TrieNode(string key, bool isAlert) {
        this->key = key;
        this->isAlert = isAlert;
    }
};
struct Trie {
    TrieNode* root;
    Trie() {
       this->root  = new TrieNode("", false); 
    }
    void addWord(string alert) {
        vector<string> tokens = split(alert);
        TrieNode* node = root;
        for(string key : tokens) {
            if(node->children.count(key) == 0) {
                node->children[key] = new TrieNode(key, false);
            }
            node = node->children[key];
        }
        node->isAlert = true;
        node->alert = alert;
    }
    void dfs(TrieNode* node, vector<string>& ans) {
        // Base case: Node is ans 
        if(node->isAlert) {
            ans.push_back(node->alert);
            return;
        }
        for(auto entry : node->children) {
            string key = entry.first;
            TrieNode* child = entry.second;
            dfs(child, ans);
        }
    }
};
vector<string> solve(vector<string> alerts) {
    Trie* trie = new Trie();
    // Build trie
    for(string alert: alerts) {
        trie->addWord(alert);
    }
    // search 
    vector<string> ans;
    trie->dfs(trie->root, ans);
    return ans;
}
int main()
{
    int t;
    cin>>t;
    for(int i=0; i < t; i++) {
        int n;
        cin >>n;
        vector<string> alerts(n);
        for(int j=0; j < n; j++) {
            cin>>alerts[j];
        }
        vector<string> ans = solve(alerts);
        for(string token: ans) {
            cout<<token<<" ";
        }
        cout<<endl;
    }

    return 0;
}

Happy coding :-)