मान लीजिए हमारे पास प्रश्नों की एक सूची है, और एक पैटर्न है, हमें एक उत्तर लौटाना होगा जो बूलियन की सूची होगी, जहां answer[i] सही है यदि और केवल यदि queries[i] पैटर्न से मेल खाता है। एक क्वेरी शब्द एक दिए गए पैटर्न से मेल खाता है जब हम पैटर्न शब्द में लोअरकेस अक्षर डाल सकते हैं ताकि यह क्वेरी के बराबर हो जाए।
उदाहरण के लिए, यदि इनपुट ["FooBar","FooBarTest","FootBall","FrameBuffer","ForceFeedBack"] और पैटर्न = "FB" जैसा है, तो परिणाम [true,false,true,false,false] होंगे।
इसे हल करने के लिए, हम निम्नलिखित चरणों का पालन करेंगे:
insertNode()नामक एक विधि परिभाषित करें, यह हेड और स्ट्रिंगsलेता हैcurr := headiको 0 सेsके आकार - 1 तक लूप करेंx := s[i]- यदि
curr का child[x]शून्य नहीं है, तोcurr का child[x] := नया नोड curr := curr का child[x]
curr का isEnd := सहीसेट करें- मुख्य विधि से, निम्नलिखित करें:
head := नया नोड, पैटर्न को हेड में डालें,n := क्वेरी सरणी का आकार,m := temp का आकार,ok := सहीjको 0 सेm - 1तक लूप करेंx := temp[j]- यदि
curr का child[x], तोcurr := curr का child[x] - अन्यथा जब
temp[j] A से Z की सीमा में है, तोok := गलतऔर लूप से ब्रेक करें 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, ]