Design Add and Search Words

# System & Data Structure Design Design problems in DSA interviews test your ability to translate requirements into a functional, efficient, and maintainable class structure. Unlike standard algorithmic problems, the focus here is on **State Management** and **API Design**. ### Core Principles 1. **Encapsulation:** Keep data private and expose functionality through well-defined methods. 2. **Trade-offs:** Every design choice has a cost. Is it better to have $O(1)$ read and $O(N)$ write, or vice versa? 3. **State Consistency:** Ensure that your internal data structures (e.g., a Map and a List) stay in sync after every operation. ### Common Design Patterns #### 1. HashMap + Doubly Linked List (DLL) The "Gold Standard" for $O(1)$ caching (LRU/LFU). ```text [Head] <-> [Node A] <-> [Node B] <-> [Node C] <-> [Tail] ^ ^ ^ ^ ^ (MRU) (Data) (Data) (Data) (LRU) ``` - **HashMap:** Provides $O(1)$ lookups for keys to their corresponding nodes. - **DLL:** Provides $O(1)$ addition/removal of nodes at both ends, maintaining the order of access. #### 2. Amortized Analysis (Rebalancing) Commonly used in **Queue using Stacks** or **Dynamic Arrays**. - Instead of doing heavy work on every call, we batch it. Pushing to a stack is $O(1)$, and "flipping" elements to another stack happens only when necessary, averaging $O(1)$ per operation. #### 3. Ring Buffers (Circular Arrays) Used for fixed-size memory management (e.g., **Circular Queue**, **Hit Counter**). ```text [0] [1] [2] [3] [4] [5] ^ ^ ^ Head (Data) Tail (Pops) (Next Push) ``` - Use `(index + 1) % capacity` to wrap around the array. #### 4. Concurrency & Thread Safety For "Hard" design problems (e.g., **Bounded Blocking Queue**). - Use **Mutexes** (Locks) to prevent data races. - Use **Condition Variables** (`wait`/`notify`) to manage producer-consumer logic efficiently without busy-waiting. ### How to Approach a Design Problem 1. **Identify the API:** What methods do you need to implement? (`get`, `put`, `push`, etc.) 2. **Define the State:** What variables represent the current state? (Size, Capacity, Pointers). 3. **Choose the Data Structures:** Select the combination that minimizes time complexity for the most frequent operations. 4. **Dry Run:** Trace the state changes through a sequence of operations based on your chosen structure.

Design Add and Search Words

Design a data structure that supports adding new words and finding if a string matches any previously added string. The search string can contain letters or dots . where a dot can match any letter.

Complexity

addWord: $O(L)$ where $L$ is word length.
search: $O(26^L)$ in worst case due to wildcards, but typically fast with Trie pruning.

Medium

Examples

Input: addWord("bad"), addWord("dad"), search("pad"), search("bad"), search(".ad"), search("b..")
Output: false, true, true, true

Approach 1

Level I: Set of Words

Intuition

Store all added words in a HashSet. For search, if it contains no dots, do an $O(1)$ lookup. If it contains dots, iterate through all words in the set ( $O(N)$ ) and check if they match the pattern.

⏱ Add: O(L), Search: O(N * L).💾 O(N * L).

java

class WordDictionary {
    Set<String> set = new HashSet<>();
    public void addWord(String word) { set.add(word); }
    public boolean search(String word) {
        if (!word.contains(".")) return set.contains(word);
        for (String s : set) {
            if (s.length() != word.length()) continue;
            boolean match = true;
            for(int i=0; i<s.length(); i++) if(word.charAt(i) != '.' && word.charAt(i) != s.charAt(i)) { match = false; break; }
            if (match) return true;
        }
        return false;
    }
}

Approach 2

Level II: HashMap of Lengths

Intuition

Group words by their length in a HashMap<Integer, Set<String>>. When searching, we only check words of the exact same length as the input, significantly reduced the comparisons.

⏱ Add: O(L), Search: O(Words_of_Length_L).💾 O(N * L).

Detailed Dry Run

Add('bad', 'dad', 'pad'). Map: {3: ['bad', 'dad', 'pad']}. Search('.ad') checks only length 3 set.

java

class WordDictionary {
    Map<Integer, Set<String>> map = new HashMap<>();
    public void addWord(String word) {
        map.putIfAbsent(word.length(), new HashSet<>());
        map.get(word.length()).add(word);
    }
    public boolean search(String word) {
        if (!map.containsKey(word.length())) return false;
        for (String s : map.get(word.length())) {
            boolean match = true;
            for (int i=0; i<word.length(); i++) if (word.charAt(i) != '.' && word.charAt(i) != s.charAt(i)) { match = false; break; }
            if (match) return true;
        }
        return false;
    }
}

Approach 3

Level III: Trie (Prefix Tree) with DFS

Intuition

Use a Trie to store words. For exact matches, search is $O(L)$ . For dots, use DFS to explore all possible children at that level.

⏱ Add: O(L), Search: O(N) where N is total Trie nodes.💾 O(N).

java

class WordDictionary {
    class Node { Node[] children = new Node[26]; boolean isEnd; }
    private Node root = new Node();
    public void addWord(String word) {
        Node curr = root;
        for (char c : word.toCharArray()) {
            if (curr.children[c-'a'] == null) curr.children[c-'a'] = new Node();
            curr = curr.children[c-'a'];
        }
        curr.isEnd = true;
    }
    public boolean search(String word) { return dfs(word, 0, root); }
    private boolean dfs(String word, int i, Node node) {
        if (i == word.length()) return node.isEnd;
        char c = word.charAt(i);
        if (c == '.') {
            for (Node child : node.children) if (child != null && dfs(word, i+1, child)) return true;
            return false;
        }
        return node.children[c-'a'] != null && dfs(word, i+1, node.children[c-'a']);
    }
}

← Previous QuestionMin Stack

Next Question →Design Underground System

Found an issue or have a suggestion?

Help us improve! Report bugs or suggest new features on our Telegram group.