Design Add and Search Word Data Structure Problem

Design Add and Search Word Data Structure Problem — ExecCode Medium DSA Practice

Solve the Design Add and Search Word Data Structure problem on ExecCode. Free online medium DSA practice in Design. Write and run code in Java, C++, Python — no signup required to run.

Problem description

Design a data structure that supports adding new words and searching for a word using addWord and search. The search operation may include the dot character '.' as a wildcard that matches any single letter, so search must try every possible child at that position instead of a single path.

Examples

Input {"ops": ["addWord", "addWord", "addWord", "search", "search", "search", "search"], "vals": ["bad", "dad", "mad", "pad", "bad", ".ad", "b.."]}; Output [None, None, None, False, True, True, True]. Input {"ops": ["addWord", "search", "search"], "vals": ["a", ".", "a"]}; Output [None, True, True]. Input {"ops": ["addWord", "addWord", "search"], "vals": ["at", "and", "a.."]}; Output [None, None, True]

Constraints

1 <= word.length <= 25 word in addWord consists of lowercase English letters word in search consists of lowercase English letters or "." At most 10^4 calls will be made to addWord and search

Practice Design Add and Search Word Data Structure free on ExecCode. Browse DSA problems, topic map, and placement guides.