solved 'Add and Search Word - Data structure design' on leetcode https://leetcode.com/problems/add-and-search-word-data-structure-design/

word_dictionary.cpp

// Use Trie + DFS for searching.
class WordDictionary {
public:

  // Add a word into the data structure.
  void addWord(string word) {
    int curr_level = 0, len = word.length();
    TrieNode *curr_level_node = &root;
    while (curr_level < len) {
      TrieNode *next_level_node = findChildNode(
          curr_level_node, word[curr_level]);
      if (!next_level_node) {
        // If not found, break and begin inserting.
        break;
      } else {
        // Otherwise follow the link.
        ++curr_level;
        curr_level_node = next_level_node;
      }
    }

    while (curr_level < len) {
      curr_level_node = insertChildNode(
          curr_level_node, word[curr_level]);
      ++curr_level;
    }
    // Mark end of word.
    curr_level_node->terminal = true;
  }

  // Return if the word is in the data structure. A word could
  // contain the dot character '.' to represent any one letter.
  bool search(string word) {
    int len = word.length();
    function<bool(struct TrieNode *, int)> traverseTrieForWord;
    traverseTrieForWord =
        [&word, &traverseTrieForWord, len](TrieNode *subroot, int i) -> bool {
      if (!subroot) {
        return false;
      }

      if (i == len) {
        // Determine whether reaches a terminal node.
        return subroot->terminal;
      }

      if (word[i] != '.') {
        return traverseTrieForWord(findChildNode(subroot, word[i]), i + 1);
      } else {
        // A wild card. Use DFS.
        TrieNode *child = subroot->child;
        while (child) {
          if (traverseTrieForWord(child, i + 1)) {
            return true;
          } else {
            child = child->next;
          }
        }
        // No string matches.
        return false;
      }
    };

    return traverseTrieForWord(&root, 0);
  }

  ~WordDictionary() {
    // Recursively delete nodes.
    if (root.child) {
      deleteNode(root.child);
    }
  }

private:
  struct TrieNode {
    TrieNode *next = nullptr;
    TrieNode *child = nullptr;
    char val = 0;
    // Indicating end of word.
    bool terminal = false;
  };

  static TrieNode *findChildNode(TrieNode *subroot, char c) {
    TrieNode *child = subroot->child;
    while (child && child->val <= c) {
      if (child->val == c) {
        return child;
      }
      else {
        child = child->next;
      }
    }
    // Didn't find the subroot matching c.
    return nullptr;
  }

  static TrieNode * insertChildNode(TrieNode *subroot, char c) {
    TrieNode *child = subroot->child, *inserted;
    if (!child || child->val > c) {
      // Insert under subroot.
      subroot->child = new TrieNode;
      inserted = subroot->child;
      inserted->val = c;
      inserted->next = child;
    } else {
      // Find an appropriate place to insert.
      while (child->next) {
        if (child->next->val < c)
          child = child->next;
        else
          break;
      }
      auto next = child->next;
      child->next = new TrieNode;
      inserted = child->next;
      inserted->val = c;
      inserted->next = next;
    }

    return inserted;
  }

  static void deleteNode(TrieNode *subroot) {
    if (subroot->next) {
      deleteNode(subroot->next);
    }
    if (subroot->child) {
      deleteNode(subroot->child);
    }
    delete subroot;
  }

  // Root node of the trie representing empty strings.
  TrieNode root;
};