資料結構
網路
關係資料庫管理系統 (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 次瀏覽
