Design add and search words data structure

String Depth-First Search Design Trie

48.2% acceptance

Jan 12, 2026

8058

491

Design a data structure that supports adding new words and finding if a string matches any previously added string. Implement the WordDictionary class: WordDictionary() Initializes the object. void addWord(word) Adds word to the data structure, it can be matched later. bool search(word) Returns true if there is any string in the data structure that matches word or false otherwise. word may contain dots '.' where dots can be matched with any letter. Example: Input ["WordDictionary","addWord","addWord","addWord","search","search","search","search"] [[],["bad"],["dad"],["mad"],["pad"],["bad"],[".ad"],["b.."]] Output [null,null,null,null,false,true,true,true] Explanation WordDictionary wordDictionary = new WordDictionary(); wordDictionary.addWord("bad"); wordDictionary.addWord("dad"); wordDictionary.addWord("mad"); wordDictionary.search("pad"); // return False wordDictionary.search("bad"); // return True wordDictionary.search(".ad"); // return True wordDictionary.search("b.."); // return True

Solution

Rust

Time O(2^n)

Space O(n)

LeetCode

solution.rs

struct WordDictTrieNode {
  children: std::collections::HashMap<char, WordDictTrieNode>,
  is_end: bool,
}

struct WordDictionary {
  root: WordDictTrieNode,
}

impl WordDictionary {
  fn new() -> Self {
    WordDictionary {
      root: WordDictTrieNode {
        children: std::collections::HashMap::new(),
        is_end: false,
      },
    }
  }
  
  fn add_word(&mut self, word: String) {
    let mut node = &mut self.root;
    for ch in word.chars() {
      node = node.children.entry(ch).or_insert(WordDictTrieNode {
        children: std::collections::HashMap::new(),
        is_end: false,
      });
    }
    node.is_end = true;
  }
  
  fn search(&self, word: String) -> bool {
    Self::search_helper(&self.root, &word.chars().collect::<Vec<_>>(), 0)
  }
  
  fn search_helper(node: &WordDictTrieNode, chars: &[char], idx: usize) -> bool {
    if idx == chars.len() {
      return node.is_end;
    }
    
    let ch = chars[idx];
    if ch == '.' {
      for (_, child) in &node.children {
        if Self::search_helper(child, chars, idx + 1) {
          return true;
        }
      }
      false
    } else {
      if let Some(child) = node.children.get(&ch) {
        Self::search_helper(child, chars, idx + 1)
      } else {
        false
      }
    }
  }
}

/*
 * Your WordDictionary object will be instantiated and called as such:
 * let obj = WordDictionary::new();
 * obj.add_word(word);
 * let ret_2: bool = obj.search(word);
 */