数据结构
网络
关系数据库管理系统 (RDBMS)
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C语言编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
服装设计
法律研究添加和搜索单词 - C++中的数据结构设计
假设我们必须设计一个支持以下两种操作的数据结构：
addWord(word)
search(word)
search(word) 方法可以搜索字面单词或仅包含字母 a-z 或 .. 的正则表达式字符串。一个 . 可以表示任何一个字母。例如，如果我们添加一些单词，如“bad”、“dad”、“mad”，则搜索 search(“pad”) → false，search(“bad”) → true，search(“.ad”) → true 和 search(“b..”) → true
为了解决这个问题，我们将遵循以下步骤：
有一些方法，首先定义 insertNode()，它将接收头引用和字符串 s，其工作原理如下：
curr := head，n := s 的大小
for i in range 0 to n – 1
x := s[i]
如果 curr 的 child[x] 不为空，则 curr 的 child[x] := 新节点
curr := curr 的 child[x]
将 curr 的 isEnd 设置为 true
从 addWord() 调用此 insertNode() 方法
定义另一个名为 check() 的方法，它将接收 curr、字符串 s 和索引。初始索引为 0。其工作原理如下：
如果索引 = s 的大小，则返回 curr 的 isEnd
设置 ok := true
如果 s[index] 是点，则
for i in range 0 to 25
x := ‘a’ 的 ASCII 码 + i
如果 curr 的 child[x] 且 check(curr 的 child[x]，s，index + 1) 为 true，则返回 true。
否则
x := s[index]
如果 curr 的 child[x] 且 check(curr 的 child[x]，s，index + 1) 为 true，则返回 true。
返回 false
在 search 方法中，设置 curr := head 并返回 check(curr, word, 0)
示例 (C++)
让我们来看下面的实现，以便更好地理解：
#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
428 次浏览
