Design Add And Search Words Data Structure

                                            
class WordDictionary {
public:
    WordDictionary() {
        root = new TrieNode();
    }
    
    void addWord(string word) {
        TrieNode* node = root;
        for (char c : word) {
            if (!node->children[c - 'a']) {
                node->children[c - 'a'] = new TrieNode();
            }
            node = node->children[c - 'a'];
        }
        node->isEnd = true;
    }

    bool search(string word) {
        return searchUtil(word, 0, root);
    }
    
private:
    struct TrieNode {
        TrieNode* children[26] = {nullptr};
        bool isEnd = false;
    };
    
    TrieNode* root;
    
    bool searchUtil(string word, int index, TrieNode* node) {
        if (index == word.length()) {
            return node->isEnd;
        }
        
        char c = word[index];
        if (c == '.') {
            for (TrieNode* child : node->children) {
                if (child && searchUtil(word, index + 1, child)) {
                    return true;
                }
            }
            return false;
        } else {
            if (!node->children[c - 'a']) {
                return false;
            }
            return searchUtil(word, index + 1, node->children[c - 'a']);
        }
    }
};

                                            
class WordDictionary {
    Map<Integer, Set<String>> map;

    public WordDictionary() {
        map = new HashMap<>();
    }

    public void addWord(String word) {
        int length = word.length();
        if (!map.containsKey(length)) {
            map.put(length, new HashSet<>());
        }
        map.get(length).add(word);
    }

    public boolean search(String word) {
        int length = word.length();
        if (!map.containsKey(length)) {
            return false;
        }

        Set<String> set = map.get(length);
        for (String str : set) {
            if (isMatch(str, word)) {
                return true;
            }
        }
        return false;
    }

    private boolean isMatch(String word, String pattern) {
        for (int i = 0; i < word.length(); i++) {
            if (pattern.charAt(i) != '.' && word.charAt(i) != pattern.charAt(i)) {
                return false;
            }
        }
        return true;
    }
}

                                            
class WordDictionary(object):
    def __init__(self):
        self.trie = {}

    def addWord(self, word):
        node = self.trie
        for letter in word:
            if letter not in node:
                node[letter] = {}
            node = node[letter]
        node['$'] = True

    def search(self, word):
        def search_in_node(word, node):
            for i, letter in enumerate(word):
                if letter not in node:
                    if letter == '.':
                        for char in node:
                            if char != '$' and search_in_node(word[i + 1:], node[char]):
                                return True
                    return False
                else:
                    node = node[letter]
            return '$' in node

        return search_in_node(word, self.trie)

                                            
typedef struct {
    bool isEnd;
    struct WordDictionary* children[26];
} WordDictionary;

WordDictionary* wordDictionaryCreate() {
    WordDictionary* obj = (WordDictionary*)malloc(sizeof(WordDictionary));
    obj->isEnd = false;
    for (int i = 0; i < 26; i++) {
        obj->children[i] = NULL;
    }
    return obj;
}

void wordDictionaryAddWord(WordDictionary* obj, char *word) {
    WordDictionary* node = obj;
    while (*word) {
        if (node->children[*word - 'a'] == NULL) {
            node->children[*word - 'a'] = wordDictionaryCreate();
        }
        node = node->children[*word - 'a'];
        word++;
    }
    node->isEnd = true;
}

bool wordDictionarySearchHelper(WordDictionary* node, char* word) {
    while (*word) {
        if (*word == '.') {
            for (int i = 0; i < 26; i++) {
                if (node->children[i] != NULL && wordDictionarySearchHelper(node->children[i], word + 1)) {
                    return true;
                }
            }
            return false;
        } else {
            if (node->children[*word - 'a'] == NULL) {
                return false;
            }
            node = node->children[*word - 'a'];
            word++;
        }
    }
    return node->isEnd;
}

bool wordDictionarySearch(WordDictionary* obj, char *word) {
    return wordDictionarySearchHelper(obj, word);
}

void wordDictionaryFree(WordDictionary* obj) {
    for (int i = 0; i < 26; i++) {
        if (obj->children[i] != NULL) {
            wordDictionaryFree(obj->children[i]);
        }
    }
    free(obj);
}

                                            
public class WordDictionary {
    private Dictionary<int, List<string>> wordDictionary;

    public WordDictionary() {
        wordDictionary = new Dictionary<int, List<string>>();
    }

    public void AddWord(string word) {
        int length = word.Length;
        if (!wordDictionary.ContainsKey(length)) {
            wordDictionary[length] = new List<string>();
        }
        wordDictionary[length].Add(word);
    }

    public bool Search(string word) {
        int length = word.Length;

        if (wordDictionary.ContainsKey(length)) {
            foreach (var w in wordDictionary[length]) {
                if (IsMatch(w, word)) {
                    return true;
                }
            }
        }

        return false;
    }

    private bool IsMatch(string s, string p) {
        if (s.Length != p.Length) {
            return false;
        }

        for (int i = 0; i < s.Length; i++) {
            if (p[i] != '.' && p[i] != s[i]) {
                return false;
            }
        }

        return true;
    }
}

                                            
var WordDictionary = function() {
    this.words = new Set();
    
    this.addWord = function(word) {
        this.words.add(word);
    };
    
    this.search = function(word) {
        for (const w of this.words) {
            if (this.match(w, word)) {
                return true;
            }
        }
        return false;
    };
    
    this.match = function(word1, word2) {
        if (word1.length !== word2.length) {
            return false;
        }
        
        for (let i = 0; i < word1.length; i++) {
            if (word1[i] !== word2[i] && word2[i] !== ".") {
                return false;
            }
        }
        
        return true;
    };
};

                                            
class WordDictionary {
    private words: Set<string>;

    constructor() {
        this.words = new Set();
    }

    addWord(word: string): void {
        this.words.add(word);
    }

    search(word: string): boolean {
        for (const w of this.words) {
            if (this.match(w, word)) {
                return true;
            }
        }
        return false;
    }

    private match(word1: string, word2: string): boolean {
        if (word1.length !== word2.length) {
            return false;
        }
        for (let i = 0; i < word1.length; i++) {
            if (word1[i] !== word2[i] && word2[i] !== '.') {
                return false;
            }
        }
        return true;
    }
}

                                            
class WordDictionary {
    private $dictionary;

    /**
     */
    function __construct() {
        $this->dictionary = [];
    }

    /**
     * @param String $word
     * @return NULL
     */
    function addWord($word) {
        $this->dictionary[$word] = true;
    }

    /**
     * @param String $word
     * @return Boolean
     */
    function search($word) {
        foreach ($this->dictionary as $dictWord => $value) {
            if (preg_match('/^' . $word . '$/', $dictWord)) {
                return true;
            }
        }
        return false;
    }
}

                                            
class WordDictionary {
    class TrieNode {
        var children = [Character: TrieNode]()
        var isEndOfWord = false
    }

    var root: TrieNode

    init() {
        root = TrieNode()
    }

    func addWord(_ word: String) {
        var node = root
        for char in word {
            if node.children[char] == nil {
                node.children[char] = TrieNode()
            }
            node = node.children[char]!
        }
        node.isEndOfWord = true
    }

    func search(_ word: String) -> Bool {
        return searchHelper(word, root)
    }

    private func searchHelper(_ word: String, _ node: TrieNode) -> Bool {
        var currentNode = node
        for (index, char) in word.enumerated() {
            if char == "." {
                for child in currentNode.children.values {
                    let newWord = String(word.suffix(word.count - index - 1))
                    if searchHelper(newWord, child) {
                        return true
                    }
                }
                return false
            } else if currentNode.children[char] == nil {
                return false
            }
            currentNode = currentNode.children[char]!
        }
        return currentNode.isEndOfWord
    }
}

                                            
class WordDictionary() {
    private val wordSet = HashSet<String>()

    fun addWord(word: String) {
        wordSet.add(word)
    }

    fun search(word: String): Boolean {
        for (w in wordSet) {
            if (isMatch(w, word)) {
                return true
            }
        }
        return false
    }

    private fun isMatch(word: String, pattern: String): Boolean {
        if (word.length != pattern.length) {
            return false
        }
        for (i in word.indices) {
            if (pattern[i] != '.' && pattern[i] != word[i]) {
                return false
            }
        }
        return true
    }
}

                                            
class WordDictionary {
  Map<int, List<String>> wordMap = Map();

  void addWord(String word) {
    int wordLength = word.length;
    if (!wordMap.containsKey(wordLength)) {
      wordMap[wordLength] = [];
    }
    wordMap[wordLength]!.add(word);
  }

  bool search(String word) {
    int wordLength = word.length;
    if (!wordMap.containsKey(wordLength)) {
      return false;
    }

    List<String> words = wordMap[wordLength]!;
    for (String w in words) {
      if (_isMatch(w, word)) {
        return true;
      }
    }
    return false;
  }

  bool _isMatch(String word, String pattern) {
    for (int i = 0; i < word.length; i++) {
      if (pattern[i] != '.' && pattern[i] != word[i]) {
        return false;
      }
    }
    return true;
  }
}

                                            
type WordDictionary struct {
    wordMap map[int][]string
}

/** Initialize your data structure here. */
func Constructor() WordDictionary {
    return WordDictionary{wordMap: make(map[int][]string)}
}

/** Adds a word into the data structure. */
func (this *WordDictionary) AddWord(word string) {
    wordLen := len(word)
    this.wordMap[wordLen] = append(this.wordMap[wordLen], word)
}

/** Returns if the word is in the data structure. A word could contain the dot character '.' to represent any one letter. */
func (this *WordDictionary) Search(word string) bool {
    wordLen := len(word)
    if _, ok := this.wordMap[wordLen]; !ok {
        return false
    }
    for _, w := range this.wordMap[wordLen] {
        if match(w, word) {
            return true
        }
    }
    return false
}

func match(s, p string) bool {
    if len(s) != len(p) {
        return false
    }
    for i := range s {
        if p[i] != '.' && p[i] != s[i] {
            return false
        }
    }
    return true
}

                                            
class WordDictionary() {
    var words: Set[String] = Set()

    def addWord(word: String): Unit = {
        words += word
    }

    def search(word: String): Boolean = {
        words.exists(w => w.length == word.length && word.zip(w).forall { case (c1, c2) => c1 == '.' || c1 == c2 })
    }
}

To solve this coding challenge, we need to design a data structure that supports the addition of new words and allows searching for words with the possibility of using '.' as a wildcard character. The most effective way to implement this is by using a Trie (prefix tree) data structure, which allows for efficient storing and searching of the strings.

Explanation

WordDictionary Class

We will create a

WordDictionary

class with the following functionalities:

Initialization : Initialize an empty Trie.
addWord() : Add a word to the Trie.
search() : Search for a word in the Trie where '.' can match any character.

Detailed Trie Structure

A Trie is a tree-like data structure that stores a dynamic set of strings, where the keys are usually strings. Each node represents a single character of the string.

Adding a Word

Start from the root.
For every character in the word, move to the corresponding child node. If it does not exist, create a new node.
Mark the end of the word.

Searching a Word

Similar to adding a word but needs to handle the '.' wildcard.
If the current character is '.', recursively search all children nodes.
If the current character is a regular character, move to the corresponding child.
At the end of the search, check if the current node marks the end of a word.

Example

Given inputs like:

                                            
["WordDictionary", "addWord", "addWord", "addWord", "search", "search", "search", "search"]
[[], ["bad"], ["dad"], ["mad"], ["pad"], ["bad"], [".ad"], ["b.."]]

The output should be:

                                            
[null, null, null, null, false, true, true, true]

Step-by-Step Explanation

Initialization :

Create an empty root node which is an empty dictionary.

Adding a Word :

Traverse each character of the word.
If the character is not in the current node, create a new dictionary for that character.
Move to the next node.
After inserting all characters, mark the end of the word by setting a special marker (e.g., '$').

Searching a Word :

Traverse each character of the word.
If the current character is '.', recursively call the search function on all child nodes.
If it's a regular character, move to that child node.
If none of the child nodes lead to a successful search, return false.
At the end, check if the current node is marked as the end of a word.

Detailed Steps in Pseudocode

Here, we illustrate the pseudocode in stages, adding comments to explain each part:

                                            
# Define the WordDictionary class
class WordDictionary:

    # Initialization method
    def __init__():
        # Initialize the root of the Trie as an empty dictionary
        root = {}

    # Method to add a word to the Trie
    def addWord(word):
        # Start from the root node
        node = root
        # Traverse each character in the word
        for character in word:
            # If the character is not yet in the current node, add it
            if character not in node:
                node[character] = {}
            # Move to the next node
            node = node[character]
        # Mark the end of the word with a special symbol, e.g., '$'
        node['$'] = True

    # Method to search for a word in the Trie
    def search(word):
        # Helper recursive function to perform search
        def search_in_node(word, node):
            # Traverse each character with its index
            for index, character in enumerate(word):
                # If character is '.' search all child nodes
                if character == '.':
                    # Recursively search all possible branches in the subsequent characters
                    for child in node:
                        # Ensure we don't match the special end marker
                        if child != '$' and search_in_node(word[index + 1:], node[child]):
                            return True
                    # If none matched, return false
                    return False
                else:
                    # If character is missing, return false
                    if character not in node:
                        return False
                    # Move to the next node
                    node = node[character]
            # Return true if the end of the word is reached,
            # indicated by presence of special end marker
            return '$' in node
        
        # Call the helper function starting from the root
        return search_in_node(word, root)

In the pseudocode above, you see that each function and its steps are clearly labeled. Make sure to understand each step and how they relate to the problem-solving process.