How to solve LeetCode 211 (Design Add and Search Words Data Structure)?

This page provides optimized solutions for LeetCode problem 211 (Design Add and Search Words Data Structure) in Java, C++, and Python, along with a detailed explanation and an interactive code editor to test and refine your code.

LeetCode 211: Design Add and Search Words Data Structure Solution

Problem Description

Explanation:

To solve this problem, we can use a Trie data structure to store the words. When adding a word, we traverse the Trie character by character and create new nodes if necessary. When searching for a word, we can use depth-first search (DFS) to match the characters of the word with the Trie nodes. If we encounter a dot ('.'), we need to explore all possible paths.

Algorithm:

Implement a TrieNode class with a HashMap to store children nodes.
Implement a WordDictionary class with methods to add a word and search for a word.
When adding a word, traverse the Trie and create nodes as needed.
When searching for a word, perform DFS with backtracking to match the characters with the Trie nodes. If a dot is encountered, explore all possible paths.
Return true if a matching word is found, false otherwise.

Time Complexity:

Adding a word: O(L), where L is the length of the word.
Searching for a word: O(26^M), where M is the number of dots in the search word.

Space Complexity:

O(N), where N is the total number of characters in all added words.

Solutions

class TrieNode {
    HashMap<Character, TrieNode> children;
    boolean isEnd;

    public TrieNode() {
        children = new HashMap<>();
        isEnd = false;
    }
}

class WordDictionary {
    private TrieNode root;

    public WordDictionary() {
        root = new TrieNode();
    }

    public void addWord(String word) {
        TrieNode node = root;
        for (char c : word.toCharArray()) {
            if (!node.children.containsKey(c)) {
                node.children.put(c, new TrieNode());
            }
            node = node.children.get(c);
        }
        node.isEnd = true;
    }

    public boolean search(String word) {
        return searchWord(word, 0, root);
    }

    private boolean searchWord(String word, int index, TrieNode node) {
        if (index == word.length()) {
            return node.isEnd;
        }

        char c = word.charAt(index);
        if (c == '.') {
            for (char key : node.children.keySet()) {
                if (searchWord(word, index + 1, node.children.get(key))) {
                    return true;
                }
            }
            return false;
        } else {
            if (node.children.containsKey(c)) {
                return searchWord(word, index + 1, node.children.get(c));
            } else {
                return false;
            }
        }
    }
}