🚀 Day 17: Trie & String Matching Pattern (Amazon Interview Series)

Amazon loves Trie-based problems because:

They simulate autocomplete search, spell-checkers, URL routing, and dictionary lookups.
Tries are highly efficient for prefix-based queries.

📝 Problem 1: Implement Trie (Prefix Tree)

👉 Amazon-style phrasing:
Design a data structure that supports insert, search, and startsWith.

Java Solution

class TrieNode {
    TrieNode[] children = new TrieNode[26];
    boolean isEndOfWord;
}

public class Trie {
    private TrieNode root;

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

    // Insert word
    public void insert(String word) {
        TrieNode node = root;
        for (char c : word.toCharArray()) {
            int idx = c - 'a';
            if (node.children[idx] == null) node.children[idx] = new TrieNode();
            node = node.children[idx];
        }
        node.isEndOfWord = true;
    }

    // Search word
    public boolean search(String word) {
        TrieNode node = root;
        for (char c : word.toCharArray()) {
            int idx = c - 'a';
            if (node.children[idx] == null) return false;
            node = node.children[idx];
        }
        return node.isEndOfWord;
    }

    // Check prefix
    public boolean startsWith(String prefix) {
        TrieNode node = root;
        for (char c : prefix.toCharArray()) {
            int idx = c - 'a';
            if (node.children[idx] == null) return false;
            node = node.children[idx];
        }
        return true;
    }
}

✅ Time Complexity: O(L) per operation, where L = length of word.
✅ Amazon relevance: Autocomplete in search, product catalog queries.

📝 Problem 2: Word Search II

👉 Amazon-style phrasing:
Given a board of letters and a list of words, return all words that can be formed.

Java Solution

import java.util.*;

class TrieNode2 {
    TrieNode2[] children = new TrieNode2[26];
    String word;
}

public class WordSearchII {
    private TrieNode2 root = new TrieNode2();
    private List<String> result = new ArrayList<>();

    // Build Trie
    public void insert(String word) {
        TrieNode2 node = root;
        for (char c : word.toCharArray()) {
            int idx = c - 'a';
            if (node.children[idx] == null) node.children[idx] = new TrieNode2();
            node = node.children[idx];
        }
        node.word = word;
    }

    public List<String> findWords(char[][] board, String[] words) {
        for (String w : words) insert(w);
        int m = board.length, n = board[0].length;

        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                dfs(board, i, j, root);
            }
        }
        return result;
    }

    private void dfs(char[][] board, int i, int j, TrieNode2 node) {
        if (i < 0 || j < 0 || i >= board.length || j >= board[0].length) return;
        char c = board[i][j];
        if (c == '#' || node.children[c - 'a'] == null) return;

        node = node.children[c - 'a'];
        if (node.word != null) {
            result.add(node.word);
            node.word = null; // avoid duplicates
        }

        board[i][j] = '#'; // mark visited
        dfs(board, i + 1, j, node);
        dfs(board, i - 1, j, node);
        dfs(board, i, j + 1, node);
        dfs(board, i, j - 1, node);
        board[i][j] = c; // restore
    }
}

✅ Time Complexity: O(M * 4^L) (M = board cells, L = word length).
✅ Amazon relevance: Pathfinding + dictionary lookup = warehouse item scanning.

📝 Problem 3: Replace Words

👉 Amazon-style phrasing:
Given a dictionary of roots, replace words in a sentence with their shortest root.

Java Solution

import java.util.*;

public class ReplaceWords {
    static class TrieNode {
        TrieNode[] children = new TrieNode[26];
        String word;
    }

    public static String replaceWords(List<String> dictionary, String sentence) {
        TrieNode root = new TrieNode();

        // Build Trie
        for (String d : dictionary) {
            TrieNode node = root;
            for (char c : d.toCharArray()) {
                int idx = c - 'a';
                if (node.children[idx] == null) node.children[idx] = new TrieNode();
                node = node.children[idx];
            }
            node.word = d;
        }

        // Replace words
        StringBuilder sb = new StringBuilder();
        for (String w : sentence.split(" ")) {
            TrieNode node = root;
            for (char c : w.toCharArray()) {
                if (node.children[c - 'a'] == null || node.word != null) break;
                node = node.children[c - 'a'];
            }
            sb.append(node.word == null ? w : node.word).append(" ");
        }
        return sb.toString().trim();
    }
}

✅ Time Complexity: O(N * L) (N = words, L = length of word).
✅ Amazon relevance: Autocorrect, product search refinement.

📝 Problem 4: Longest Word in Dictionary

👉 Amazon-style phrasing:
Return the longest word that can be built one character at a time by other words in the dictionary.

Java Solution

import java.util.*;

public class LongestWordInDictionary {
    public static String longestWord(String[] words) {
        Arrays.sort(words);
        Set<String> built = new HashSet<>();
        String res = "";
        for (String w : words) {
            if (w.length() == 1 || built.contains(w.substring(0, w.length()-1))) {
                built.add(w);
                if (w.length() > res.length()) res = w;
            }
        }
        return res;
    }
}

✅ Time Complexity: O(N log N + N*L).
✅ Amazon relevance: Word chain validation.

🎯 Key Takeaways

Tries are must-know for string and dictionary problems.
They optimize search, prefix checks, and word matching.
Amazon loves to combine Tries with DFS/BFS for grid problems.
Classic questions:
- Implement Trie
- Word Search II
- Replace Words
- Longest Word in Dictionary