쿼리 목록과 패턴이 있다고 가정하고 부울 목록이 될 답변을 반환해야 합니다. 여기서 쿼리[i]가 패턴과 일치하는 경우에만 answer[i]가 true입니다. 쿼리 단어는 쿼리와 동일하도록 패턴 단어에 소문자를 삽입할 수 있는 경우 주어진 패턴과 일치합니다.
따라서 입력이 ["FooBar","FooBarTest","FootBall","FrameBuffer","ForceFeedBack"]이고 패턴 ="FB"인 경우 결과는 [true,false,true,false,false]가 됩니다. .
이 문제를 해결하기 위해 다음 단계를 따릅니다. −
-
insertNode()라는 메서드를 정의합니다. 이것은 머리와 문자열을 사용합니다.
-
커 :=머리
-
범위 0에서 s – 1까지의 i에 대해
-
x :=s[i]
-
curr의 자식[x]가 null이 아니면 curr의 자식[x] :=새 노드
-
curr :=curr의 자식[x]
-
-
set isEnd of curr :=true
-
기본 방법에서 다음을 수행하십시오 -
-
head :=새 노드, 헤드에 패턴 삽입, n :=쿼리 배열 크기, m :=임시 크기, ok :=true
-
0 ~ m – 1 범위의 j에 대해
-
x :=온도[j]
-
curr의 자식[x]이면 curr :=curr의 자식[x]
-
그렇지 않으면 temp[j]가 A~Z 범위에 있으면 ok :=false이고 fromloop을 끊습니다.
-
ans[i] :=isEnd of curr AND ok
-
-
반환
예시(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, ]