Design Add and Search Words Data Structure

NeetCode: Design Add and Search Words Data Structure · LeetCode: 211. Design Add and Search Words Data Structure · Difficulty: Medium

Design a WordDictionary with addWord(word) and search(word). The stored words use lowercase letters. The searched word may contain ., which matches any single letter.

Example

Text

addWord("day"); addWord("bay"); addWord("may")
search("say")  -> false
search("day")  -> true
search(".ay")  -> true
search("b..")  -> true

Brute force: test the pattern against every word

Keep every word in a List<String>. A word matches the pattern when the lengths are equal and every position is either . or the same character.

Java

import java.util.ArrayList;
import java.util.List;

class WordDictionary {
    private final List<String> words = new ArrayList<>();

    public WordDictionary() {}

    public void addWord(String word) {
        words.add(word);
    }

    public boolean search(String pattern) {
        for (String w : words) {
            if (matches(w, pattern)) return true;
        }
        return false;
    }

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

public class Main {
    public static void main(String[] args) {
        WordDictionary dict = new WordDictionary();
        for (String w : new String[] {"day", "bay", "may"}) {
            dict.addWord(w);
        }
        System.out.println(dict.search("say"));
        System.out.println(dict.search("day"));
        System.out.println(dict.search(".ay"));
        System.out.println(dict.search("b.."));
    }
}

Output

false
true
true
true

Time: O(N · L) per search. Space: O(N · L).

Optimal: trie with DFS on wildcards

Store the words in a trie: each node holds an array of 26 child references (null when absent) and an end-of-word flag, and the child for letter c is at index c - 'a'. For a normal letter, follow that one child. For ., try every existing child and succeed if any branch matches the rest of the pattern. Without wildcards a search is O(L); each . multiplies the work by the branching factor, limited to nodes that exist.

Java

class TrieNode {
    TrieNode[] children = new TrieNode[26];
    boolean isEnd;
}

class WordDictionary {
    private final TrieNode root = new TrieNode();

    public WordDictionary() {}

    public void addWord(String word) {
        TrieNode node = root;
        for (int i = 0; i < word.length(); i++) {
            int c = word.charAt(i) - 'a';
            if (node.children[c] == null) node.children[c] = new TrieNode();
            node = node.children[c];
        }
        node.isEnd = true;
    }

    public boolean search(String pattern) {
        return matches(root, pattern, 0);
    }

    // Does the pattern from index i onward match some path below node?
    private boolean matches(TrieNode node, String pattern, int i) {
        if (i == pattern.length()) return node.isEnd;
        char ch = pattern.charAt(i);
        if (ch == '.') {
            for (TrieNode child : node.children) {
                if (child != null && matches(child, pattern, i + 1)) return true;
            }
            return false;
        }
        TrieNode child = node.children[ch - 'a'];
        return child != null && matches(child, pattern, i + 1);
    }
}

public class Main {
    public static void main(String[] args) {
        WordDictionary dict = new WordDictionary();
        for (String w : new String[] {"day", "bay", "may"}) {
            dict.addWord(w);
        }
        System.out.println(dict.search("say"));
        System.out.println(dict.search("day"));
        System.out.println(dict.search(".ay"));
        System.out.println(dict.search("b.."));
        System.out.println(dict.search("..."));
        System.out.println(dict.search("...."));
    }
}

Output

false
true
true
true
true
false

Time: addWord is O(L). search is O(L) for exact patterns and up to O(26^d · L) worst case for d wildcards. Space: O(total letters).