Last updated on July 18th, 2024 at 04:17 am

Here, We see Design Add and Search Words Data Structure LeetCode Solution. This Leetcode problem is done in many programming languages like C++, Java, JavaScript, Python, etc. with different approaches.

List of all LeetCode Solution

Topics

Backtracking, Design, Trie

Companies

Facebook

Level of Question

Medium

Design Add and Search Words Data Structure LeetCode Solution

Problem Statement

Design a data structure that supports adding new words and finding if a string matches any previously added string.

Implement the WordDictionary class:

• WordDictionary() Initializes the object.
• void addWord(word) Adds word to the data structure, it can be matched later.
• bool search(word) Returns true if there is any string in the data structure that matches word or false otherwise. word may contain dots '.' where dots can be matched with any letter.

Example:
Input [“WordDictionary”,”addWord”,”addWord”,”addWord”,”search”,”search”,”search”,”search”] [[],[“bad”],[“dad”],[“mad”],[“pad”],[“bad”],[“.ad”],[“b..”]]
Output [null,null,null,null,false,true,true,true]
Explanation
WordDictionary wordDictionary = new WordDictionary();
wordDictionary.addWord(“bad”);
wordDictionary.addWord(“dad”);
wordDictionary.addWord(“mad”);
wordDictionary.search(“pad”); // return False
wordDictionary.search(“bad”); // return True
wordDictionary.search(“.ad”); // return True
wordDictionary.search(“b..”); // return True

1. Design Add and Search Words Data Structure LeetCode Solution C++

class TrieNode {
public:
    bool word;
    TrieNode* children[26];
    TrieNode() {
        word = false;
        memset(children, NULL, sizeof(children));
    }
};

class WordDictionary {
public:
    WordDictionary() {
        
    }
    
    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 -> word = true;
    }
    
    bool search(string word) {
        return search(word.c_str(), root);
    }
private:
    TrieNode* root = new TrieNode();
    bool search(const char* word, TrieNode* node) {
        for (int i = 0; word[i] && node; i++) {
            if (word[i] != '.') {
                node = node -> children[word[i] - 'a'];
            } else {
                TrieNode* tmp = node;
                for (int j = 0; j < 26; j++) {
                    node = tmp -> children[j];
                    if (search(word + i + 1, node)) {
                        return true;
                    }
                }
            }
        }
        return node && node -> word;
    }
};

2. Design Add and Search Words Data Structure LeetCode Solution Java

class WordDictionary {
    private WordDictionary[] children;
    boolean isEndOfWord;
    public WordDictionary() {
        children = new WordDictionary[26];
        isEndOfWord = false;
    }
    
    public void addWord(String word) {
        WordDictionary curr = this;
        for(char c: word.toCharArray()){
            if(curr.children[c - 'a'] == null)
                curr.children[c - 'a'] = new WordDictionary();
            curr = curr.children[c - 'a'];
        }
        curr.isEndOfWord = true;
    }
    
    public boolean search(String word) {
        WordDictionary curr = this;
        for(int i = 0; i < word.length(); ++i){
            char c = word.charAt(i);
            if(c == '.'){
                for(WordDictionary ch: curr.children)
                    if(ch != null && ch.search(word.substring(i+1))) return true;
                return false;
            }
            if(curr.children[c - 'a'] == null) return false;
            curr = curr.children[c - 'a'];
        }
        return curr != null && curr.isEndOfWord;
    }
}

3. Design Add and Search Words Data Structure LeetCode Solution JavaScript

class Node{
    constructor(){
        this.keys = new Map();
        this.end = false;
    }
    setEnd(){this.end = true;}
    isEnd(){return this.end}
}

var WordDictionary = function() {
    this.root = new Node();
};

WordDictionary.prototype.addWord = function(word) {
    let node = this.root;
    function rec(node, word){
        if(word){
            if(!node.keys.has(word[0]))
                node.keys.set(word[0], new Node());
            return rec(node.keys.get(word[0]), word.substr(1));
        }
        else node.setEnd();
    }
    rec(node, word)
    return true;
};

WordDictionary.prototype.search = function(word) {
    let node = this.root;
    function rec(node, word){
        if(!node) return false;
        if(word){
			if(word[0]==='.'){
                let out = false;
                for(let val of node.keys.keys()){
                    out = out || rec(node.keys.get(val), word.substr(1));
                }
                return out;
            }
            else if(node.keys.has(word[0])){
                return rec(node.keys.get(word[0]), word.substr(1));
            }
            else{ return false}
            
        }
        else return node.isEnd();
    }
    return rec(node, word);
};

4. Design Add and Search Words Data Structure LeetCode Solution Python

class WordDictionary(object):

    def __init__(self):
        self.children = [None]*26
        self.isEndOfWord = False
        
    def addWord(self, word):
        curr = self
        for c in word:
            if curr.children[ord(c) - ord('a')] == None:
                curr.children[ord(c) - ord('a')] = WordDictionary()
            curr = curr.children[ord(c) - ord('a')]
        curr.isEndOfWord = True;
        
    def search(self, word):
        curr = self
        for i in range(len(word)):
            c = word[i]
            if c == '.':
                for ch in curr.children:
                    if ch != None and ch.search(word[i+1:]): return True
                return False
            if curr.children[ord(c) - ord('a')] == None: return False
            curr = curr.children[ord(c) - ord('a')]
        return curr != None and curr.isEndOfWord