Leetcode 211. 添加与搜索单词 - 数据结构设计

题目

设计一个支持以下两种操作的数据结构：

void addWord(word)
bool search(word)
search(word) 可以搜索文字或正则表达式字符串，字符串只包含字母 . 或 a-z 。 . 可以表示任何一个字母。

示例:

addWord("bad")
addWord("dad")
addWord("mad")
search("pad") -> false
search("bad") -> true
search(".ad") -> true
search("b..") -> true

说明:

你可以假设所有单词都是由小写字母 a-z 组成的。

C++解法

class WordDictionary {
public:
    vector<int16_t> indices = {-1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1};
    vector<vector<int16_t>> tries;
    set<int> words;
    WordDictionary() {
        tries.push_back(indices);
    }
    
    void addWord(const string & word) {
        if (!word.empty()) addWord(0, word, 0);
    }
    
    void addWord(int trie_index, const string & word, const int i) {
        if (tries[trie_index][word[i] - 'a'] == -1) {
            tries[trie_index][word[i] - 'a'] = (int)tries.size();
            tries.push_back(indices);
        }
        if (i != word.size() - 1) {
           addWord(tries[trie_index][word[i] - 'a'], word, i+1);
        } else {
            words.insert(trie_index);
        }
    }
    
    bool search(const string & word) {
        bool succeed = false;
        searchWord(0, word, 0, succeed);
        return succeed;
    }
    
    void searchWord(int trie_index, const string & word, const int i, bool & succeed) {
        if (succeed) return;
        if (word[i] != '.' && (tries[trie_index][word[i] - 'a'] == -1)) {
            return;
        }
        if (i != word.size() - 1) {
            if (word[i] != '.') {
                if (tries[trie_index][word[i] - 'a'] != -1) {
                    searchWord(tries[trie_index][word[i] - 'a'], word, i + 1, succeed);
                }
            } else {
                for (int j = 0; j < 26; ++j) {
                    if (tries[trie_index][j] != -1) searchWord(tries[trie_index][j], word, i + 1, succeed);
                }
            }
        } else {
            succeed = words.count(trie_index);
        }
    }
};

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/add-and-search-word-data-structure-design
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。