211. Design Add and Search Words Data Structure

Description

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.

Constraints

• 1 <= word.length <= 500

• word in addWord consists lower-case English letters.

• word in search consist of '.' or lower-case English letters.

• At most 50000 calls will be made to addWord and search.

Approach

Links

• GeeksforGeeks

• Leetcode

• ProgramCreek

• YouTube

Examples

Example 1

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

Solutions

Solution 1

/**
 * Time complexity : O(M), where M is the key length. At each 
 *    step, we either examine or create a node in the trie. 
 *    That takes only M operations.
 * Space complexity : O(M). In the worst-case newly inserted 
 *    key doesn't share a prefix with the keys already 
 *    inserted in the trie. We have to add M new nodes, 
 *    which takes O(M) space.
 */

class WordDictionary {
    private Map<Integer, Set<String>> dict;

    /** Initialize your data structure here. */
    public WordDictionary() {
        dict = new HashMap();
    }
    
    /** Adds a word into the data structure. */
    public void addWord(String word) {
        int m = word.length();
        if(!dict.containsKey(m)) {
            dict.put(m, new HashSet());
        }
        dict.get(m).add(word);
    }
    
    /** Returns if the word is in the data structure. 
        A word could contain the dot character '.' to 
        represent any one letter. */
    public boolean search(String word) {
        int m = word.length();
        if(dict.containsKey(m)) {
            for(String w: dict.get(m)) {
                int i = 0;
                while(i < m && 
                        (w.charAt(i) == word.charAt(i) || 
                        word.charAt(i) == '.')) {
                    i++;
                }
                if(i == m) return true;
            }
        }
        return false;
    }
}

/**
 * Your WordDictionary object will be instantiated and 
 * called as such:
 * WordDictionary obj = new WordDictionary();
 * obj.addWord(word);
 * boolean param_2 = obj.search(word);
 */

Solution 2

/**
 * Time complexity : 
 * Space complexity : 
 */

class TrieNode {
    Map<Character, TrieNode> children = new HashMap();
    boolean word = false;
    public TrieNode() {}
}

class WordDictionary {
    TrieNode trie;

    /** Initialize your data structure here. */
    public WordDictionary() {
        trie = new TrieNode();
    }
    
    /** Adds a word into the data structure. */
    public void addWord(String word) {
        TrieNode node = trie;
        
        for (char ch : word.toCharArray()) {
            if (!node.children.containsKey(ch)) {
                node.children.put(ch, new TrieNode());
            }
            node = node.children.get(ch);
        }
        node.word = true;
    }
    
    /** Returns if the word is in the node. */
    public boolean searchInNode(String word, TrieNode node) {
        for (int i = 0; i < word.length(); ++i) {
            char ch = word.charAt(i);
            if (!node.children.containsKey(ch)) {
                // if the current character is '.'
                // check all possible nodes at this level
                if (ch == '.') {
                    for (char x : node.children.keySet()) {
                        TrieNode child = node.children.get(x);
                        if (searchInNode(word.substring(i + 1), child)) {
                            return true;    
                        }    
                    }   
                }
                // if no nodes lead to answer
                // or the current character != '.'
                return false;    
            } else {
                // if the character is found
                // go down to the next level in trie
                node = node.children.get(ch); 
            }   
        }      
        return node.word;
    }

    /** Returns if the word is in the data structure. A word could contain the dot character '.' to represent any one letter. */
    public boolean search(String word) {
        return searchInNode(word, trie);
    }
}

Follow up