C++에서 문자열에 크기 K의 모든 이진 코드가 포함되어 있는지 확인

<시간/>

이진 문자열 s와 정수 k가 있다고 가정합니다. 길이가 k인 모든 이진 코드가 s의 부분 문자열인지 확인해야 합니다. 그렇지 않으면 False를 반환합니다.

따라서 입력이 S ="00110110", k =2와 같으면 출력은 true가 됩니다. 길이가 2인 바이너리 코드는 "00", "01", "10" 및 "11"입니다. 이들은 각각 인덱스 0, 1, 3, 2에 있습니다.

이 문제를 해결하기 위해 다음 단계를 따릅니다. −

한 세트 v
정의
temp :=빈 문자열
필요 :=2^k
initialize i :=0의 경우 i
- 온도 :=온도 + s[i]
- i>=k이면 -
  - temp의 첫 번째 인덱스에서 한 문자 삭제
- i>=k - 1이면 -
  - v
    에 temp 삽입
- v의 크기가 req와 같으면 -
  - true를 반환
거짓을 반환

예시

더 나은 이해를 위해 다음 구현을 살펴보겠습니다. −

#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