C++ 中的 Camelcase 匹配
c++server side programmingprogramming更新于 2024/9/1 5:55:00
假设我们有一个查询列表和一个模式，我们必须返回一个布尔值列表的答案，其中当且仅当查询 [i] 与模式匹配时，answer[i] 才为真。当我们可以将小写字母插入模式词以使其等于查询时，查询词与给定模式匹配。
因此，如果输入类似于 ["FooBar","FooBarTest","FootBall","FrameBuffer","ForceFeedBack"] 且 pattern = "FB"，则结果将为 [true,false,true,false,false]。
为了解决这个问题，我们将遵循以下步骤 −
定义一个名为 insertNode() 的方法，它需要 head 和字符串 s
curr := head
for i in range 0 to size of s – 1
x := s[i]
如果 curr 的 child[x] 不为空，则 curr 的 child[x] := 新节点
curr := child[x] of curr
设置 curr 的 isEnd := true
从主方法中，执行以下操作 −
head := 新节点，将模式插入 head，n := 查询数组的大小，m := temp 的大小，ok := true
对于 j 在 0 到 m 的范围内 – 1
x := temp[j]
如果 child[x] of curr，则 curr := child[x] of curr
否则，当 temp[j] 在 A 到 Z 范围内时，ok := false 并从循环中中断
ans[i] := isEnd of curr AND ok
return 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, ]
