algoadvance

Leetcode 211. Design Add and Search Words Data Structure

Problem Statement

You need to design a data structure for adding and searching words efficiently. The data structure should support the following two operations:

1. void addWord(String word): Adds a word into the data structure.
2. boolean search(String word): Returns true if the word is in the data structure. A word could contain the dot character '.' to represent any one letter.

Clarifying Questions

1. Q: How large can the words be?
   • A: The length of each word is in the range [1, 500].
2. Q: How many words can we add to the data structure?
   • A: You can assume the number of words added will not exceed 3 * 10^4.
3. Q: Can the dot character '.' appear multiple times in a single search query?
   • A: Yes, the '.' character can appear multiple times and at any positions within the search query.
4. Q: Should the search operation support case sensitivity?
   • A: For simplicity, assume all input words are lowercase.

Strategy

We will use a Trie (prefix tree) data structure. This will help us efficiently store and search words with support for the dot character '.'.

• Adding a Word:
  • We will insert each word character by character into the Trie. Each node in the Trie will represent a character of a word.
  • Mark the end of the word with a boolean flag.
• Searching a Word:
  • Implement a recursive depth-first search (DFS) to handle the dot character. The dot character indicates that we must check all possible characters at that position.
  • For normal characters, simply follow the Trie branch.

Code

Here’s how you can implement the data structure in Java:

class WordDictionary {

    private class TrieNode {
        public TrieNode[] children;
        public boolean isWord;

        public TrieNode() {
            this.children = new TrieNode[26]; // for 26 lowercase English letters
            this.isWord = false;
        }
    }
    
    private TrieNode root;

    public WordDictionary() {
        this.root = new TrieNode();
    }
    
    public void addWord(String word) {
        TrieNode node = root;
        for (char c : word.toCharArray()) {
            int index = c - 'a';
            if (node.children[index] == null) {
                node.children[index] = new TrieNode();
            }
            node = node.children[index];
        }
        node.isWord = true; // mark the end of a word
    }
    
    public boolean search(String word) {
        return searchInNode(word, root, 0);
    }

    private boolean searchInNode(String word, TrieNode node, int start) {
        TrieNode current = node;
        for (int i = start; i < word.length(); i++) {
            char c = word.charAt(i);
            if (c == '.') {
                // Check all possible children nodes
                for (TrieNode child : current.children) {
                    if (child != null && searchInNode(word, child, i + 1)) {
                        return true;
                    }
                }
                return false; // if no path matched
            } else {
                int index = c - 'a';
                if (current.children[index] == null) {
                    return false;
                }
                current = current.children[index];
            }
        }
        return current.isWord;
    }
}

Time Complexity

• addWord(String word):
  • Time complexity: O(n) where n is the length of the word. This is because we iterate over each character of the word once and perform constant time operations.
• search(String word):
  • Time complexity: In the worst case, it can be O(26^m * n) where m is the length of the word and n is the number of characters processed. The worst case occurs because each '.' character requires checking all 26 possible children nodes.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI

• Got blindsided by a question you didn’t expect?

• Spend too much time studying?

• Or simply don’t have the time to go over all 3000 questions?