Tries and Adapting Data Structures

• A Trie (pronounced “try”) is a tree-like data structure used to efficiently store and search strings (like words). It’s sometimes called a prefix tree, because it stores data based on common prefixes.

• Each node represents a character, and a path from the root to a node spells out a prefix of some word.

• Uses partitions of strings.

• Was originally used to help search when computer were dumb back in the day.

• “Adapting” data structures means tweaking or combining them to better fit your problem.

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

struct TrieNode {
    bool isEnd;
    unordered_map<char, TrieNode*> children;

    TrieNode() : isEnd(false) {}
};

class Trie {
private:
    TrieNode* root;

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

    void insert(const string &word) {
        TrieNode* node = root;
        for (char ch : word) {
            if (!node->children[ch])
                node->children[ch] = new TrieNode();
            node = node->children[ch];
        }
        node->isEnd = true;
    }

    bool search(const string &word) {
        TrieNode* node = root;
        for (char ch : word) {
            if (!node->children.count(ch))
                return false;
            node = node->children[ch];
        }
        return node->isEnd;
    }

    bool startsWith(const string &prefix) {
        TrieNode* node = root;
        for (char ch : prefix) {
            if (!node->children.count(ch))
                return false;
            node = node->children[ch];
        }
        return true;
    }
};

int main() {
    Trie trie;
    trie.insert("cat");
    trie.insert("car");

    cout << trie.search("cat") << endl;      // 1 (true)
    cout << trie.search("cap") << endl;      // 0 (false)
    cout << trie.startsWith("ca") << endl;   // 1 (true)
}