Practice/Microsoft/Leetcode 211. Design Add and Search Words Data Structure

Leetcode 211. Design Add and Search Words Data Structure

CodingOptional

Problem

Design a word dictionary data structure that supports two operations:

1. addWord(word): Adds a word to the dictionary
2. search(word): Searches for a word in the dictionary, where the search pattern can contain the wildcard character '.' that matches any single letter

The wildcard '.' can appear multiple times in a search pattern and at any position. For example, if "bad" is in the dictionary, then searching for ".ad", "b.d", and "ba." should all return true.

Requirements

1. Implement the WordDictionary class with an __init__ method (constructor)
2. Implement addWord(word) that adds a word to the dictionary (returns None/void)
3. Implement search(word) that returns true if the word or any matching pattern exists in the dictionary
4. The '.' character in search patterns must match exactly one letter
5. Words consist only of lowercase English letters
6. The pattern length must match the word length exactly (wildcards don't match zero or multiple characters)

Constraints

• 1 ≤ word.length ≤ 25
• word in addWord consists of lowercase English letters
• word in search consists of lowercase English letters and '.' wildcards
• There will be at most 10,000 calls to addWord and search combined
• Time complexity should be efficient for repeated searches

Examples

Example 1:

` Operations: ["WordDictionary", "addWord", "addWord", "addWord", "search", "search", "search", "search"] Arguments: [[], ["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 (not in dictionary) wordDictionary.search("bad"); // return True (exact match) wordDictionary.search(".ad"); // return True (matches "bad", "dad", "mad") wordDictionary.search("b.."); // return True (matches "bad") `

Example 2:

` Operations: ["WordDictionary", "addWord", "search", "search", "search"] Arguments: [[], ["test"], ["...."], ["..."], ["t..."]] Output: [null, null, true, false, true]

Explanation: wordDictionary.addWord("test"); wordDictionary.search("...."); // return True (4 wildcards match "test") wordDictionary.search("..."); // return False (3 chars don't match 4-char word) wordDictionary.search("t..."); // return True (matches "test") `