使用 C++ 检查字符串是否包含所有长度为 K 的二进制代码
c++server side programmingprogramming
假设我们有一个二进制字符串 s 和一个整数 k。我们必须检查长度为 k 的每个二进制代码是否都是 s 的子字符串。否则,返回 False。
因此,如果输入为 S = "00110110",k = 2,则输出将为 True。长度为 2 的二进制代码为 "00"、"01"、"10" 和 "11"。它们分别位于索引 0、1、3 和 2 处。
为了解决这个问题,我们将遵循以下步骤 −
定义一个集合 v
temp := 空字符串
req := 2^k
初始化 i := 0,当 i < s 的大小,更新(将 i 增加 1),执行 −
temp := temp + s[i]
如果 i >= k,则 −
从 temp 的第一个索引中删除一个字符
如果 i >= k - 1,则 −
将 temp 插入 v
如果 v 的大小与 req 相同,则 −
return true
return false
示例
让我们看下面的实现,以便更好地理解 −
#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