数据结构
网络
关系数据库管理系统 (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 次浏览
广告