Course4all

Design Add and Search Words

Expert Answer & Key Takeaways

# 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)O(1) read and O(N)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)O(1) caching (LRU/LFU). ```text [Head] <-> [Node A] <-> [Node B] <-> [Node C] <-> [Tail] ^ ^ ^ ^ ^ (MRU) (Data) (Data) (Data) (LRU) ``` - HashMap: Provides O(1)O(1) lookups for keys to their corresponding nodes. - DLL: Provides O(1)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)O(1), and "flipping" elements to another stack happens only when necessary, averaging O(1)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)O(L) where LL is word length.
  • search: O(26L)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)O(1) lookup. If it contains dots, iterate through all words in the set (O(N)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)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']);
    }
}

Course4All Technical Board

Verified Expert

Senior Software Engineers & Algorithmic Experts

Our DSA content is authored and reviewed by engineers from top tech firms to ensure optimal time and space complexity analysis.

Pattern: 2026 Ready
Updated: Weekly
← Previous QuestionMin Stack
Next Question →Design Underground System