資料結構
網路
關係資料庫管理系統 (RDBMS)
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
服裝設計
法學C++中的駝峰式匹配
假設我們有一系列查詢和一個模式，我們需要返回一個布林值列表作為答案，其中answer[i]為真當且僅當queries[i]與模式匹配。當我們可以將小寫字母插入模式詞使其等於查詢詞時，查詢詞與給定模式匹配。
因此，如果輸入類似於["FooBar","FooBarTest","FootBall","FrameBuffer","ForceFeedBack"]並且模式為"FB"，則結果將為[true,false,true,false,false]。
為了解決這個問題，我們將遵循以下步驟：
定義一個名為insertNode()的方法，它接受頭節點和字串s作為引數。
curr := 頭節點
對於i從0到s的長度減1迴圈
x := s[i]
如果curr的子節點child[x]不為空，則curr的子節點child[x] := 新節點
curr := curr的子節點child[x]
設定curr的isEnd := true
在主方法中，執行以下操作：
head := 新節點，將模式插入head，n := 查詢陣列的長度，m := temp的長度，ok := true
對於j從0到m減1迴圈
x := temp[j]
如果curr存在子節點child[x]，則curr := curr的子節點child[x]
否則，如果temp[j]在A到Z範圍內，則ok := false並跳出迴圈
ans[i] := curr的isEnd AND ok
返回ans
示例(C++)
讓我們來看下面的實現，以便更好地理解：
#include <bits/stdc++.h>
using namespace std;
void print_vector(vector<auto> v){
cout << "[";
for(int i = 0; i<v.size(); i++){
cout << v[i] << ", ";
}
cout << "]"<<endl;
}
struct Node{
bool isEnd;
map <char, Node*> child;
Node(){
isEnd = false;
}
};
class Solution {
public:
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]){
curr->child[x] = new Node();
}
curr = curr->child[x];
}
curr->isEnd = true;
}
vector<bool> camelMatch(vector<string>& queries, string pattern){
Node* head = new Node();
insertNode(head, pattern);
int n = queries.size();
vector <bool> ans(n);
Node* curr;
bool ok;
for(int i = 0; i < n; i++){
string temp = queries[i];
curr = head;
int m = temp.size();
ok = true;
for(int j = 0; j < m; j++){
char x = temp[j];
if(curr->child[x]){
curr = curr->child[x];
}
else if(temp[j] >= 'A' && temp[j] <= 'Z'){
ok = false;
break;
}
}
ans[i] = curr->isEnd && ok;
}
return ans;
}
};
main(){
vector<string> v1 = {"FooBar","FooBarTest","FootBall","FrameBuffer","ForceFeedBack"};
Solution ob;
print_vector(ob.camelMatch(v1, "FB"));
}輸入
["FooBar","FooBarTest","FootBall","FrameBuffer","ForceFeedBack"] "FB"
輸出
[1, 0, 1, 1, 0, ]
更新於：2020年5月2日
709 次瀏覽
廣告