C++实现LeetCode(211.添加和查找单词-数据结构设计)

首先，我们需要先了解一下题目的要求和限制，以及具体的解题思路。

题目描述

设计一个支持添加、删除、查找单词的数据结构。添加和删除单词的操作需要支持普通词和通配符'.'。查找单词只支持普通词，不支持通配符'.'。所有单词都是非空的。

解题思路

这道题可以使用前缀树（Trie树）来实现。

首先，我们需要定义一个单词类，它包含两个字段：单词字符串和单词长度。然后，我们需要构建一个前缀树，每个节点包含一个字母和指向下一层节点的指针数组。在添加单词时，我们需要把单词的每个字母插入到前缀树中。如果遇到通配符'.'，则需要把当前节点的全部子节点都加入到搜索列表中。

在查找单词时，我们需要从根节点开始遍历前缀树，一边遍历一边比对单词的每个字母。如果遇到通配符'.'，则需要在搜索列表中搜索。如果最后遍历到的节点是一个单词节点，则说明存在该单词。

Code

下面是C++的完整代码。

#include <iostream>
#include <string>
#include <vector>
using namespace std;

class Word {
public:
    string str;
    int len;
    Word(string s) {
        str = s;
        len = s.length();
    }
};

class TrieNode {
public:
    TrieNode* next[26];
    vector<int> words;
    TrieNode() {
        for (int i = 0; i < 26; i++) {
            next[i] = nullptr;
        }
    }
};

class WordDictionary {
public:
    TrieNode* root;
    WordDictionary() {
        root = new TrieNode();
    }

    void addWord(string word) {
        TrieNode* p = root;
        for (int i = 0; i < word.length(); i++) {
            int index = word[i] - 'a';
            if (p->next[index] == nullptr) {
                p->next[index] = new TrieNode();
            }
            p = p->next[index];
            p->words.push_back(i);
        }
    }

    bool search(string word) {
        Word w(word);
        return dfs(w, 0, root);
    }

    bool dfs(Word& word, int pos, TrieNode* node) {
        if (pos == word.len) {
            return node != nullptr && !node->words.empty();
        }
        if (word.str[pos] == '.') {
            for (int i = 0; i < 26; i++) {
                if (node->next[i] != nullptr) {
                    if (dfs(word, pos + 1, node->next[i])) {
                        return true;
                    }
                }
            }
        } else {
            int index = word.str[pos] - 'a';
            if (node->next[index] != nullptr) {
                if (dfs(word, pos + 1, node->next[index])) {
                    return true;
                }
            }
        }
        return false;
    }
};

int main() {
    WordDictionary wd;
    string word1 = "bad";
    string word2 = "dad";
    string word3 = "mad";
    wd.addWord(word1);
    wd.addWord(word2);
    wd.addWord(word3);
    cout << wd.search("pad") << endl;  // return false
    cout << wd.search("bad") << endl;  // return true
    cout << wd.search(".ad") << endl;  // return true
    cout << wd.search("b..") << endl;  // return true
    cout << wd.search("bda") << endl;  // return false
    return 0;
}

示例说明

示例1：

输入：
WordDictionary wd;
wd.addWord("bad");
wd.addWord("dad");
wd.addWord("mad");
wd.search("pad");
wd.search("bad");
wd.search(".ad");
wd.search("b..");
wd.search("bda");
输出：
false
true
true
true
false

示例2：

输入：
WordDictionary wd;
wd.addWord("apple");
wd.search("apple");   // 返回 true
wd.search("app");     // 返回 false
wd.addWord("app");
wd.search("app");     // 返回 true
输出：
true
false
true