假设我们必须设计一个支持以下两个操作的数据结构-
addWord(word)
搜索（单词）
search(word)方法可以搜索仅包含字母az或.. A的文字单词或正则表达式字符串。表示它可以代表任何一个字母。因此，例如，如果我们添加一些单词，例如“ bad”，“ dad”，“ mad”，然后搜索search（“ pad”）→false，search（“ bad”）→true，search（“。ad”） →true，然后搜索（“ b ..”）→true
为了解决这个问题，我们将遵循以下步骤-
有一些方法，最初定义insertNode()，将使用head引用和字符串s，这将如下工作：
curr：= head，n：= s的大小
对于i，范围为0至n – 1
x：= s [i]
如果curr的child [x]不为null，则curr的child [x]：=新节点
curr：= curr的子级[x]
将curr的isEnd设置为true
从中addWord()，调用此insertNode()方法
定义另一个方法check()，该方法将使用curr，string和index。初始索引为0。这将如下工作-
如果index = s的大小，则返回curr的isEnd
设置好：= true
如果s [index]是点，则
x：='a'+ i的ASCII
如果curr的child [x]和check（curr，s，index + 1的child [x]）为true，则返回true。
当我在0到25的范围内
除此以外
x：= s [index]
如果curr的child [x]和check（curr，s，index + 1的child [x]）为true，则返回true。
返回假
从搜索方法中，设置curr：= head并返回check(curr,word,0)
让我们看下面的实现以更好地理解-
#include <bits/stdc++.h>
using namespace std;
struct Node{
bool isEnd;
map <char, Node*> child;
Node(){
isEnd = false;
}
};
class WordDictionary {
public:
Node* head;
WordDictionary() {
head = new Node();
}
void insertNode(Node* head, string s){
Node* curr = head;
int n = s.size();
for(int i = 0; i < n; i++){
char x = s[i];
if(!curr->child[x]){
curr->child[x] = new Node();
}
curr = curr->child[x];
}
curr->isEnd = true;
}
void addWord(string word) {
insertNode(head, word);
}
bool check(Node* curr, string s, int idx = 0){
if(idx == s.size()) return curr->isEnd;
bool ok = false;
if(s[idx] == '.'){
for(int i = 0; i < 26; i++){
char x = 'a' + i;
if(curr->child[x] && check(curr->child[x], s, idx + 1))return true;
}
} else {
char x = s[idx];
if(curr->child[x] && check(curr->child[x], s, idx + 1))return true;
}
return false;
}
bool search(string word) {
Node* curr = head;
return check(curr, word);
}
};
main(){
WordDictionary ob;
ob.addWord("bad");
ob.addWord("dad");
ob.addWord("mad");
cout << (ob.search("pad")) << endl;
cout << (ob.search("bad")) << endl;
cout << (ob.search(".ad")) << endl;
cout << (ob.search("b..")) << endl;
}Initialize the WordDictionary, then call the addWord() methods ans search methods. See in the main() function
输出结果
0 1 1 1