สมมติว่าเรามีสตริงไบนารี s และจำนวนเต็ม k เราต้องตรวจสอบว่าทุกรหัสไบนารีที่มีความยาว k เป็นสตริงย่อยของ s หรือไม่ มิเช่นนั้นให้คืนค่าเป็นเท็จ
ดังนั้น หากอินพุตเป็น S ="00110110", k =2 เอาต์พุตจะเป็นจริง รหัสเลขฐานสองที่มีความยาว 2 คือ "00", "01", "10" และ "11" มีอยู่ในดัชนี 0, 1, 3 และ 2 ตามลำดับ
เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -
-
กำหนดหนึ่งชุด v
-
temp :=สตริงว่าง
-
ต้องการ :=2^k
-
สำหรับการเริ่มต้น i :=0 เมื่อ i
-
temp :=temp + s[i]
-
ถ้า i>=k แล้ว −
-
ลบอักขระหนึ่งตัวออกจากดัชนีแรกของอุณหภูมิ
-
-
ถ้า i>=k - 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
