मान लीजिए एक पहेली स्ट्रिंग है, एक शब्द वैध है यदि निम्नलिखित दोनों शर्तें मान्य हैं:
शब्द में पहेली का पहला अक्षर होता है।
शब्द के प्रत्येक अक्षर के लिए, वह अक्षर पहेली में होता है।
मान लीजिए यदि हम एक उदाहरण पर विचार करते हैं कि, यदि पहेली "abcdefg" की तरह है, तो वैध शब्द "face", "cabbage" आदि हैं; लेकिन कुछ अमान्य शब्द "beefed" हैं क्योंकि इसमें "a" नहीं है और "based" क्योंकि इसमें "s" है जो पहेली में मौजूद नहीं है।
हमें उत्तरों की सूची ज्ञात करनी है, जहां answer[i] दिए गए शब्द सूची words में उन शब्दों की संख्या है जो पहेली puzzles[i] के संबंध में वैध हैं।
यदि इनपुट words = ["aaaa","asas","able","ability","actt","actor","access"], puzzles = ["aboveyz","abrodyz","abslute","absoryz","actresz","gaswxyz"] है, तो आउटपुट [1,1,3,2,4,0] होगा, क्योंकि "aboveyz" के लिए एक वैध शब्द: "aaaa", "abrodyz" के लिए एक: "aaaa", "abslute" के लिए तीन: "aaaa", "asas", "able", "absoryz" के लिए दो: "aaaa", "asas", "actresz" के लिए चार: "aaaa", "asas", "actt", "access" और "gaswxyz" के लिए कोई वैध शब्द नहीं क्योंकि सूची में कोई भी शब्द 'g' अक्षर नहीं रखता।
हल करने के चरण
getMask() फ़ंक्शन परिभाषित करें जो स्ट्रिंग का बिटमास्क बनाता है
मुख्य विधि से: सभी शब्दों के लिए बिटमास्क बनाएं और उनकी आवृत्ति गिनें
प्रत्येक पहेली के लिए: इसका बिटमास्क बनाएं, पहला अक्षर का बिट निकालें
सबमास्क गणना का उपयोग करके वैध शब्दों की गणना करें: current = mask, while current > 0: यदि current में पहला बिट है तो आवृत्ति जोड़ें, current = (current-1) & mask
उत्तर सरणी लौटाएं
उदाहरण
#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;
}
typedef long long int lli;
class Solution {
public:
lli getMask(string s) {
lli mask = 0;
for(int i = 0; i < s.size(); i++) {
mask |= 1LL << (s[i] - 'a');
}
return mask;
}
vector<int> findNumOfValidWords(vector<string>& w, vector<string>& p) {
vector<int> ans;
map<lli, lli> m;
for(int i = 0; i < w.size(); i++) {
string word = w[i];
lli mask = 0;
for(int j = 0; j < word.size(); j++) {
mask |= getMask(w[i]);
}
m[mask]++;
}
for(int i = 0; i < p.size(); i++) {
string word = p[i];
lli mask = getMask(word);
lli first = 1LL << (word[0] - 'a');
lli current = mask;
lli temp = 0;
while(current > 0) {
if(current & first) temp += m[current];
current = (current - 1) & mask;
}
ans.push_back(temp);
}
return ans;
}
};
int main() {
Solution ob;
vector<string> v = {"aaaa","asas","able","ability","actt","actor","access"};
vector<string> v1 = {"aboveyz","abrodyz","abslute","absoryz","actresz","gaswxyz"};
print_vector(ob.findNumOfValidWords(v, v1));
return 0;
}
इनपुट
{"aaaa","asas","able","ability","actt","actor","access"}, {"aboveyz","abrodyz","abslute","absoryz","actresz","gaswxyz"}
आउटपुट
[1, 1, 3, 2, 4, 0, ]