Giả sử chúng ta có một chuỗi nhị phân s và một số nguyên k. Chúng ta phải kiểm tra xem mọi mã nhị phân có độ dài k có phải là một chuỗi con của s hay không. Nếu không, trả về False.
Vì vậy, nếu đầu vào là S ="00110110", k =2, thì đầu ra sẽ là true. Các mã nhị phân có độ dài 2 là "00", "01", "10" và "11". Chúng có mặt lần lượt ở các chỉ số 0, 1, 3 và 2.
Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -
-
Xác định một bộ v
-
temp:=chuỗi trống
-
yêu cầu:=2 ^ k
-
để khởi tạo i:=0, khi i
-
temp:=temp + s [i]
-
nếu tôi> =k, thì -
-
xóa một ký tự khỏi chỉ mục đầu tiên của tạm thời
-
-
nếu tôi> =k - 1, thì -
-
chèn tạm thời vào v
-
-
nếu kích thước của v giống với yêu cầu thì -
-
trả về true
-
-
-
trả về false
Ví dụ
Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -
#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));
} Đầu vào
"00110110",2
Đầu ra
1