資料結構
網路
關係資料庫管理系統(RDBMS)
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
服裝學
法學C++中的字元流
假設我們想實現如下所示的StreamChecker類：
StreamChecker(words) − 這是建構函式，它使用給定的單詞初始化資料結構。
query(letter) − 當對於某些 k >= 1，最後 k 個查詢的字元（按照從舊到新的順序，包括剛剛查詢的這個字母）拼寫出給定列表中的某個單詞時，返回 true。
因此，如果輸入類似於單詞列表 = ["ce", "g", "lm"]，然後對 [a,b,c,e,f,g,h,i,j,k,l,m] 多次呼叫 query，則輸出對於 e、g、m 為 true，對於其他字元為 false。
為了解決這個問題，我們將遵循以下步驟：
定義一個節點結構，其中包含一個大小為 26 的節點陣列和一個isEnd標誌
最初 isEnd 為 false，子陣列填充為 null。
定義一個節點頭head
建立一個節點陣列waitList
定義一個函式insertNode()，它將接收head和s作為引數。
curr := head
對於初始化 i := 0，當 i < s 的大小，更新（i 增加 1），執行：
x := s[i]
如果 curr 的 child[x - 'a'] 不為 null，則：
curr.child[x - 'a'] = 建立一個新的節點Node
curr := curr.child[x - 'a']
curr 的 isEnd := true
從初始化器執行此操作
head := 建立一個新節點
對於初始化 i := 0，當 i < words 的大小，更新（i 增加 1），執行：
insertNode(head, words[i])
curr := head
定義一個函式 query()，它將接收 x 作為引數。
建立一個節點陣列 temp
如果 head.child[x - 'a']，則：
將 head 插入 waitList 的末尾
ret := false
對於初始化 i := 0，當 i < waitList 的大小，更新（i 增加 1），執行：
curr := waitList[i]
如果 curr.child[x - 'a']，則
curr := curr 的 child[x - 'a']
將 curr 插入 temp 的末尾
ret := ret OR curr 的 isEnd
swap(temp, waitList)
返回 ret
讓我們看看下面的實現來更好地理解：
示例
#include <bits/stdc++.h>
using namespace std;
struct Node {
Node* child[26];
bool isEnd;
Node(){
isEnd = false;
for (int i = 0; i < 26; i++)
child[i] = NULL;
}
};
class StreamChecker {
public:
Node* head;
vector<Node*> waitList;
void insertNode(Node* head, string& s){
Node* curr = head;
for (int i = 0; i < s.size(); i++) {
char x = s[i];
if (!curr->child[x - 'a']) {
curr->child[x - 'a'] = new Node();
}
curr = curr->child[x - 'a'];
}
curr->isEnd = true;
}
StreamChecker(vector<string>& words){
head = new Node();
for (int i = 0; i < words.size(); i++) {
insertNode(head, words[i]);
}
Node* curr = head;
}
bool query(char x){
vector<Node*> temp;
if (head->child[x - 'a']) {
waitList.push_back(head);
}
bool ret = false;
for (int i = 0; i < waitList.size(); i++) {
Node* curr = waitList[i];
if (curr->child[x - 'a']) {
curr = curr->child[x - 'a'];
temp.push_back(curr);
ret |= curr->isEnd;
}
}
swap(temp, waitList);
return ret;
}
};
main(){
vector<string> v = {"ce","g","lm"};
StreamChecker ob(v);
cout << (ob.query('a')) << endl;
cout << (ob.query('b')) << endl;
cout << (ob.query('c')) << endl;
cout << (ob.query('e')) << endl;
cout << (ob.query('f')) << endl;
cout << (ob.query('g')) << endl;
cout << (ob.query('h')) << endl;
cout << (ob.query('i')) << endl;
cout << (ob.query('j')) << endl;
cout << (ob.query('k')) << endl;
cout << (ob.query('l')) << endl;
cout << (ob.query('m'));
}輸入
"ce","g","lm", query(),
輸出
0 0 0 1 0 1 0 0 0 0 0 1
476 次瀏覽
