使用 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

相关文章