211. Add and Search Word - Data structure design

Design a data structure that supports the following two operations:

void addWord(word)

bool search(word)

search(word) can search a literal word or a regular expression string containing only letters a-z or .. A . means it can represent any one letter.

For example:

addWord("bad")

addWord("dad")

addWord("mad")

search("pad") -> false

search("bad") -> true

search(".ad") -> true

search("b..") -> true

Note:

You may assume that all words are consist of lowercase letters a-z.

Thoughts

查字典里是否出现给定的一系列单词，单词中的'.'可代表任意字符。和普通trie的区别在于有"."能代表任意字符，利用DFS遍历所有的子树直到找到。DFS时当前结点是pos指定的字符的父节点，因此当循环完单词后节点就是最后一个字符所代表的节点，检查它是否是单词结束。

Code

/*
 * @lc app=leetcode id=211 lang=cpp
 *
 * [211] Add and Search Word - Data structure design
 */

// @lc code=start
class WordDictionary {
public:
    class TrieNode {
    public:
        char val;
        bool end;
        unordered_map<char, TrieNode*> children;
        TrieNode(char v, bool e): val(v), end(e) {}
    };
    TrieNode *root;
    /** Initialize your data structure here. */
    WordDictionary() {
        root = new TrieNode('-', false);
    }
    
    /** Adds a word into the data structure. */
    void addWord(string word) {
        TrieNode *cur = root;
        for (int i = 0; i < word.length(); ++i) {
            const auto c = word[i];
            if (!cur->children.count(c)) cur->children[c] = new TrieNode(c, false);
            cur = cur->children[c];
            if (i == word.length() - 1) cur->end = true;
        }
    }
    
    bool dfs(TrieNode *cur, string &word, int pos) {
        for (; pos < word.length(); ++pos) {
            const auto c = word[pos];
            if (c == '.') {
                for (const auto &p : cur->children) {
                    if (dfs(p.second, word, pos + 1)) {
                        return true;
                    }
                }
                return false;
            } else {
                if (!cur->children.count(c)) return false;
                cur = cur->children[c];
            }
        }
        return cur->end;
    }
    /** Returns if the word is in the data structure. A word could contain the dot character '.' to represent any one letter. */
    bool search(string word) {
        return dfs(root, word, 0);
    }
};

/**
 * Your WordDictionary object will be instantiated and called as such:
 * WordDictionary* obj = new WordDictionary();
 * obj->addWord(word);
 * bool param_2 = obj->search(word);
 */
// @lc code=end

class WordDictionary {

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

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

    /** Adds a word into the data structure. */
    public void addWord(String word) {
        TrieNode node = root;
        for (int i = 0; i < word.length(); i++) {
            int index = word.charAt(i) - 'a';
            if (node.children[index] == null) {
                node.children[index] = new TrieNode();
            }
            node = node.children[index];
        }

        node.word = true;
    }

    private boolean search(String word, int start, TrieNode node) {
        for (int i = start; i < word.length(); i++) {
            if (word.charAt(i) == '.') {
                for (int j = 0; j < 26; j++) {
                    if (node.children[j] != null && search(word, i + 1, node.children[j])) {
                        return true;
                    }
                }
                return false;
            } else {
                int index = word.charAt(i) - 'a';
                if (node.children[index] == null) {
                    return false;
                }
                node = node.children[index];
            }
        }

        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 search(word, 0, root);
    }
}

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

Analysis

Errors: 1. 没有在backtracking循环后写return false.

search的时间复杂度T(l) = 26 T(l - 1) = 26 26 * T(l - 2)...因此是O(26 ^ l). 插入还是O(l).