मान लीजिए कि हमारे पास एक बाइनरी स्ट्रिंग s और एक पूर्णांक k है। हमें यह जांचना है कि लंबाई k का प्रत्येक बाइनरी कोड s का विकल्प है या नहीं। अन्यथा, झूठी वापसी करें।
इसलिए, यदि इनपुट S ="00110110", k =2 जैसा है, तो आउटपुट सत्य होगा। लंबाई 2 के बाइनरी कोड "00", "01", "10" और "11" हैं। ये क्रमशः 0, 1, 3 और 2 सूचकांकों पर मौजूद हैं।
इसे हल करने के लिए, हम इन चरणों का पालन करेंगे -
-
एक सेट को परिभाषित करें v
-
अस्थायी:=रिक्त स्ट्रिंग
-
अनुरोध :=2^के
-
इनिशियलाइज़ करने के लिए:=0, जब i <साइज़ ऑफ़ s, अपडेट (i से 1 तक बढ़ाएँ), करें -
-
अस्थायी:=अस्थायी + एस [i]
-
अगर मैं>=के, तो -
-
अस्थायी की पहली अनुक्रमणिका से एक वर्ण हटाएं
-
-
अगर मैं>=के -1, तो -
-
v
. में अस्थायी डालें
-
-
यदि v का आकार req के समान है, तो -
-
सही लौटें
-
-
-
झूठी वापसी
उदाहरण
आइए एक बेहतर समझ प्राप्त करने के लिए निम्नलिखित कार्यान्वयन देखें -
#include <bits/stdc++.h>
using namespace std;
typedef long long int lli;
class Solution {
public:
lli fastPow(lli b, lli p){
lli ret = 1;
while (p) {
if (p & 1) {
ret *= b;
}
b *= b;
p >>= 1;
}
return ret;
}
bool hasAllCodes(string s, int k) {
unordered_set<string> v;
string temp = "";
lli req = fastPow(2, k);
for (lli i = 0; i < s.size(); i++) {
temp += s[i];
if (i >= k) {
temp.erase(0, 1);
}
if (i >= k - 1) {
v.insert(temp);
}
if ((lli)v.size() == req)
return true;
}
return false;
}
};
main(){
Solution ob;
cout << (ob.hasAllCodes("00110110",2));
} इनपुट
"00110110",2
आउटपुट
1