dsa/strings | desc: Trie Data Structure

trie.cpp

class Node {
  public:
    vector<Node*> children;
    bool isLeaf;
    Node() {
      children.assign(26, NULL);
      isLeaf = false;
    }
};

class Trie {
public:
  Node *root;
  /** Initialize your data structure here. */
  Trie() {
    root = new Node();
  }
  
  /** Inserts a word into the trie. */
  void insert(string word) {
    Node *node = root;
    for (int i = 0; i < word.length(); i++) {
      int idx = word[i] - 'a';
      if (!node -> children[idx])
        node -> children[idx] = new Node();
      node = node -> children[idx];
    }
    node -> isLeaf = true;
  }
  
  /** Returns if the word is in the trie. */
  bool search(string word) {
    Node *node = root;
    for (int i = 0; i < word.length(); i++) {
      int idx = word[i] - 'a';
      if (!node -> children[idx])
        return false;
      node = node -> children[idx];
    }
    return node -> isLeaf == true;
  }
  
  /** Returns if there is any word in the trie that starts with the given prefix. */
  bool startsWith(string prefix) {
    Node *node = root;
    for (int i = 0; i < prefix.length(); i++) {
      int idx = prefix[i] - 'a';
      if (!node -> children[idx])
        return false;
      node = node -> children[idx];
    }
    return true;
  }
};

• Maximum XOR of Two Numbers in an Array - Trie + Bitmasking