What is the time and space complexity of Design Add and Search Words Data Structure?

Time complexity: O(L) average, O(L * alphabet) worst. Space complexity: O(total characters).

Design Add and Search Words Data Structure

Med

Concept

Code

Loading editor...

Tap Analyze to see visualization

Click Analyze to visualize

See step-by-step execution, variables, and output

Variables

Run code to see variables

Output

Console output will appear here

Press Space to start•← → to step•? all shortcuts

Solution Guide: Design Add and Search Words Data Structure

Approach

Store all words in trie. For wildcard '.', branch over every child at that trie depth with DFS/backtracking.

Complexity Analysis

Time: O(L) average, O(L * alphabet) worst
Space: O(total characters)

Pattern

Trie with DFS Wildcards

Why It Works

Literal words follow a single path. Wildcards branch to all children, which is equivalent to checking every matching character transition at that level.

Updated Feb 2026