algoadvance

Leetcode 211. Design Add and Search Words Data Structure

Problem Statement

Design a data structure that supports the following two operations:

  1. void addWord(word): Adds a word into the data structure.
  2. bool search(word): Returns true if there is any string in the data structure that matches word or false otherwise. The word may contain dots '.' where dots can be matched with any letter.

Implement the WordDictionary class:

class WordDictionary {
public:
    WordDictionary();
    void addWord(string word);
    bool search(string word);
};

Clarifying Questions

  1. Input Constraints:
    • Are there any limits on the length of the word?
    • Can we assume that inputs are valid and contain only lowercase English letters or dots?
  2. Performance Requirements:
    • What should be the average and worst-case time complexity for addWord and search functions?

Strategy

  1. Data Structure Choice:
    • Use a Trie (prefix tree) to store the added words. The Trie will allow for efficient insertion and search operations.
  2. Handling the Dot '.':
    • During the search operation, if a dot is encountered, it means any letter from ‘a’ to ‘z’ can replace the dot. We need to check all possible branches in the Trie at this position.
  3. Trie Node Design:
    • Each Trie node will have an array of 26 pointers (for each letter of the alphabet) and a boolean to indicate if the node marks the end of a word.

Code Implementation

#include <iostream>
#include <string>
#include <vector>

using namespace std;

class TrieNode {
public:
    bool isWord;
    TrieNode* children[26];

    TrieNode() : isWord(false) {
        for (int i = 0; i < 26; ++i) {
            children[i] = nullptr;
        }
    }
};

class WordDictionary {
private:
    TrieNode* root;
    
    bool searchInNode(string& word, int index, TrieNode* node) {
        if (index == word.length()) {
            return node->isWord;
        }
        char c = word[index];
        if (c == '.') {
            for (int i = 0; i < 26; ++i) {
                if (node->children[i] && searchInNode(word, index + 1, node->children[i])) {
                    return true;
                }
            }
            return false;
        } else {
            int childIndex = c - 'a';
            return node->children[childIndex] && searchInNode(word, index + 1, node->children[childIndex]);
        }
    }

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

    void addWord(string word) {
        TrieNode* currentNode = root;
        for (char c : word) {
            int index = c - 'a';
            if (!currentNode->children[index]) {
                currentNode->children[index] = new TrieNode();
            }
            currentNode = currentNode->children[index];
        }
        currentNode->isWord = true;
    }

    bool search(string word) {
        return searchInNode(word, 0, root);
    }
};

// Example usage:
// int main() {
//     WordDictionary wordDictionary;
//     wordDictionary.addWord("bad");
//     wordDictionary.addWord("dad");
//     wordDictionary.addWord("mad");
//     cout << wordDictionary.search("pad") << endl; // Should return false
//     cout << wordDictionary.search("bad") << endl; // Should return true
//     cout << wordDictionary.search(".ad") << endl; // Should return true
//     cout << wordDictionary.search("b..") << endl; // Should return true
//     return 0;
// }

Time Complexity

Space Complexity

This design leverages the Trie structure to efficiently manage and search words, providing flexibility to handle the dot wildcard in the search queries effectively.

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