#211 Leetcode Design Add and Search Words Data Structure Solution in C, C++, Java, JavaScript, Python, C# Leetcode

Algorithm

Problem Name: 211. Design Add and Search Words Data Structure

Problem Link: https://leetcode.com/problems/design-add-and-search-words-data-structure/

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

Constraints:

1 <= word.length <= 25
word in addWord consists of lowercase English letters.
word in search consist of '.' or lowercase English letters.
There will be at most 3 dots in word for search queries.
At most 10⁴ calls will be made to addWord and search.

Code Examples

#1 Code Example with C Programming

Code - C Programming


typedef struct dict_s {
    int is_leaf;
    struct dict_s *child[26];
} WordDictionary;

/** Initialize your data structure here. */
WordDictionary* wordDictionaryCreate() {
    WordDictionary *obj;
    
    obj  = calloc(1, sizeof(WordDictionary));
    //assert(obj);
    
    return obj;
}

/** Adds a word into the data structure. */
void wordDictionaryAddWord(WordDictionary* obj, char* word) {
    int k;
    
    if (!word || !*word) return;
    
    while (*word) {
        k = *word - 'a';
        if (!obj->child[k]) {
            obj->child[k] = calloc(1, sizeof(WordDictionary));
            //assert(obj->child[k]);
        }
        obj = obj->child[k];
        word ++;
    }
    obj->is_leaf = 1;
}

/** Returns if the word is in the data structure. A word could contain the dot character '.' to represent any one letter. */
bool wordDictionarySearch(WordDictionary* obj, char* word) {
    int k;
    
    while (obj && *word) {
        if (*word == '.') {
            for (k = 0; k  <  26; k ++) {
                if (wordDictionarySearch(obj->child[k], word + 1)) {
                    return true;
                }
            }
            return false;
        } else {
            k = *word - 'a';
            obj = obj->child[k];
            word ++;
        }
    }
    
    return (obj && obj->is_leaf) ? true : false;
}

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

Copy The Code & Try With Live Editor

Input

–

cmd

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

Output

–

cmd

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

#2 Code Example with C++ Programming

Code - C++ Programming


class WordDictionary {
public:
    WordDictionary() {}
    
    void addWord(string word) {
        words[word.size()].push_back(word);
    }
    
    bool search(string word) {
        for(auto s: words[word.size()]) if(isEqual(s, word)) return true;
        return false;
    }
    
private:
    unordered_map<int, vector < string>>words;
    
    bool isEqual(string a, string b){
        for(int i = 0; i  <  a.size(); i++){
            if(b[i] == '.') continue;
            if(a[i] != b[i]> return false;
        }
        return true;
    }
};

Copy The Code & Try With Live Editor

Input

–

cmd

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

Output

–

cmd

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

#3 Code Example with Java Programming

Code - Java Programming


class WordDictionary {
  
  private Node root;
  
  public WordDictionary() {
    this.root = new Node();
  }

  public void addWord(String word) {
    Node curr = root;
    for (char c : word.toCharArray()) {
      if (curr.children[c - 'a'] == null) {
        curr.children[c - 'a'] = new Node();
      }
      curr = curr.children[c - 'a'];
    }
    curr.isWord = true;
  }

  public boolean search(String word) {
    Node curr = root;
    return searchHelper(word, 0, curr);
  }
  
  private boolean searchHelper(String word, int idx, Node curr) {
    if (idx == word.length()) {
      return curr.isWord;
    }
    if (word.charAt(idx) != '.' && curr.children[word.charAt(idx) - 'a'] == null) {
      return false;
    }
    if (word.charAt(idx) == '.') {
      for (Node child : curr.children) {
        if (child != null && searchHelper(word, idx + 1, child)) {
          return true;
        }
      }
      return false;
    }
    return searchHelper(word, idx + 1, curr.children[word.charAt(idx) - 'a']);
  }
  
  private static class Node {
    Node[] children;
    boolean isWord;
    
    public Node() {
      this.children = new Node[26];
      this.isWord = false;
    }
  }
}

Copy The Code & Try With Live Editor

Input

–

cmd

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

Output

–

cmd

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

#4 Code Example with Javascript Programming

Code - Javascript Programming


class TrieNode {
  constructor() {
    this.children = [];
    this.isWord = false;
  }
}

const WordDictionary = function() {
  this.root = new TrieNode();
  this.aCode = "a".charCodeAt(0);
};

/**
 * Adds a word into the data structure.
 * @param {string} word
 * @return {void}
 */
WordDictionary.prototype.addWord = function(word) {
  let node = this.root;
  for (let c of word.split("")) {
    let code = c.charCodeAt(0);
    if (node.children[code - this.aCode] == null) {
      node.children[code - this.aCode] = new TrieNode();
    }
    node = node.children[code - this.aCode];
  }
  node.isWord = true;
};

/**
 * Returns if the word is in the data structure. A word could contain the dot character '.' to represent any one letter.
 * @param {string} word
 * @return {boolean}
 */
WordDictionary.prototype.search = function(word) {
  return this._match(word.split(""), 0, this.root);
};
WordDictionary.prototype._match = function(arr, k, node) {
  if (k == arr.length) {
    return node && node.isWord;
  }
  if (arr[k] === ".") {
    for (let i = 0; node != null && i  <  node.children.length; i++) {
      if (
        node.children[i] !== null &&
        this._match(arr, k + 1, node.children[i])
      ) {
        return true;
      }
    }
  } else {
    return (
      node != null && node.children[arr[k].charCodeAt(0) - this.aCode] != null &&
      this._match(arr, k + 1, node.children[arr[k].charCodeAt(0) - this.aCode])
    );
  }
  return false;
};

Copy The Code & Try With Live Editor

Input

–

cmd

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

Output

–

cmd

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

#5 Code Example with Python Programming

Code - Python Programming


class TrieNode:
    def __init__(self):
        self.children = [None] * 26
        self.last = False
class WordDictionary:

    def __init__(self):
        """
        Initialize your data structure here.
        """
        self.root = TrieNode()

    def addWord(self, word):
        """
        Adds a word into the data structure.
        :type word: str
        :rtype: void
        """
        curr = self.root
        for char in word:
            if not curr.children[ord(char) - ord("a")]: curr.children[ord(char) - ord("a")] = TrieNode()
            curr = curr.children[ord(char) - ord("a")]
        curr.last = True
    def search(self, word):
        """
        Returns if the word is in the data structure. A word could contain the dot character '.' to represent any one letter.
        :type word: str
        :rtype: bool
        """
        words = [self.root]
        for char in word:
            if char == ".": words = [child for node in words for child in node.children if node and child]
            else: words = [node.children[ord(char) - ord("a")] for node in words if node and node.children[ord(char) - ord("a")]]
        if words and words[-1] == ".": return True
        else: return any([node.last for node in words if node.last])

Copy The Code & Try With Live Editor

Input

–

cmd

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

Output

–

cmd

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

#6 Code Example with C# Programming

Code - C# Programming


using System.Collections.Generic;

namespace LeetCode
{
    public class _0211_AddAndSearchWordDataStructureDesign
    {
        private readonly Trie root;

        /** Initialize your data structure here. */
        public _0211_AddAndSearchWordDataStructureDesign()
        {
            root = new Trie();
        }

        /** Adds a word into the data structure. */
        public void AddWord(string word)
        {
            var current = root;
            foreach (var ch in word)
            {
                if (!current.Children.ContainsKey(ch))
                    current.Children.Add(ch, new Trie());
                current = current.Children[ch];
            }

            current.Finished = true;
        }

        /** Returns if the word is in the data structure. A word could contain the dot character '.' to represent any one letter. */
        public bool Search(string word)
        {
            return Search(word, root);
        }

        private bool Search(string word, Trie startPoint)
        {
            var current = startPoint;
            for (int i = 0; i  <  word.Length; i++)
            {
                var ch = word[i];
                if (ch == '.')
                {
                    foreach (var key in current.Children.Keys)
                    {
                        if (Search(word.Substring(i + 1), current.Children[key]))
                            return true;
                    }
                    return false;
                }
                else if (current.Children.ContainsKey(ch))
                    current = current.Children[ch];
                else
                    return false;
            }

            return current.Finished;
        }

        private class Trie
        {
            public Dictionary < char, Trie> Children = new Dictionary();
            public bool Finished = false;
        }
    }

Copy The Code & Try With Live Editor

Input

–

cmd

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

Output

–

cmd

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

Demonstration

Previous
#210 Leetcode Course Schedule II Solution in C, C++, Java, JavaScript, Python, C# Leetcode

Next
#212 Leetcode Word Search II Solution in C, C++, Java, JavaScript, Python, C# Leetcode

Try With Live Editor

Category - Leetcode Online Judge Maniruzzaman Akash 1 year ago 541 0