Tries tree

What is Trie?

Trie is a type of k-ary search tree used for storing and searching a specific key from a set. Using Trie, search complexities can be brought to optimal limit (key length). 

In the realm of computer science, data structures reign supreme, each with its unique strengths and applications. Amongst these champions stands the trie, a tree-like marvel specifically designed for storing and manipulating strings. Whether you're tackling intricate search queries, suggesting autocompletions, or correcting embarrassing typos, tries prove their mettle across diverse scenarios.

Delving into the Trie's Roots

Imagine a tree, not with leaves rustling in the breeze, but with characters occupying its branches. Each level represents a position in a string, and the characters branching out signify the possible next characters. This is the essence of a trie.

Let's take the words "cat," "car," and "can" as an example. In a trie, 'c' would be the root node, branching into 'a' (leading to "cat"), 'a' (leading to "car"), and 'an' (ultimately forming "can"). This structure reflects the shared prefix and divergences in these strings.

Unlocking the Power of Tries:

• Efficient Search: Finding a specific string in a trie is like navigating the tree. If you reach a dead end, the string doesn't exist; otherwise, you've found your match! This process typically takes the length of the string, much faster than searching an entire list.
• Prefix Matches: What if you need strings starting with "ca"? No problem! Start at the root, follow the 'c' branch, and then the 'a' branch. All words reachable from this point (e.g., "care," "cape") have the desired prefix.
• Autocompletion and Spell Checking: As you type, tries can suggest the most likely word based on the characters entered so far. They can also identify potential typos by suggesting words within the trie that are similar to the one you're typing.

Real-World Applications:

• Search engines: Tries power autocomplete features and help with spell checking queries.
• Spell checkers: By efficiently storing correct words, tries aid in catching typos and suggesting alternatives.
• Network routing: Tries can efficiently direct data packets to their destinations based on prefix matches.
• Biological and linguistic analyses: Tries are useful for searching and analyzing DNA sequences, language models, and other string-based data.

Beyond the Basics:

While tries excel at string operations, they can also store integers or other data types by representing them as strings. However, it's important to consider trie's potential memory usage, as storing many strings can create a large structure.

Example

public class Trie {

    private TrieNode root;

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

    // Insert a string into the trie
    public void insert(String word) {
        TrieNode current = root;
        for (char c : word.toCharArray()) {
            TrieNode nextNode = current.children.get(c);
            if (nextNode == null) {
                nextNode = new TrieNode();
                current.children.put(c, nextNode);
            }
            current = nextNode;
        }
        current.isWord = true; // Mark the end of the word
    }

    // Search for a complete word in the trie
    public boolean search(String word) {
        TrieNode current = root;
        for (char c : word.toCharArray()) {
            TrieNode nextNode = current.children.get(c);
            if (nextNode == null) {
                return false; // Word not found
            }
            current = nextNode;
        }
        return current.isWord; // Check if the current node marks the end of the word
    }

    // Check if a prefix exists in the trie
    public boolean startsWith(String prefix) {
        TrieNode current = root;
        for (char c : prefix.toCharArray()) {
            TrieNode nextNode = current.children.get(c);
            if (nextNode == null) {
                return false; // Prefix not found
            }
            current = nextNode;
        }
        return true; // Prefix found
    }

    // Trie node class
    private static class TrieNode {
        Map<Character, TrieNode> children = new HashMap<>();
        boolean isWord;
    }
}

See

https://medium.com/@rohitverma_87831/my-interview-experience-at-google-afc1080df175

https://medium.com/@rohitverma_87831/my-interview-experience-at-meta-ad7eb22dd220

https://medium.com/@rohitverma_87831/my-interview-experience-at-amazon-offer-sde-ii-6223edbd4fa3Trie | (Insert and Search) - GeeksforGeeks