C++: Trie with linked list + DFS


  • 0
    E

    I've seen many good answers using Trie but most of them hardcode 26 children for a single Trie node. The following snippets is another implementation of Trie using singly linked list.

    // Use Trie + DFS for searching.
    class WordDictionary {
    public:
    
      // Adds 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;
      }
    
      // Returns 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;
    };

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.