C++에서 1에서 N을 나타내는 부분 문자열이 있는 이진 문자열

이진 문자열 S와 양의 정수 N이 있다고 가정하고 1에서 N까지의 모든 정수 X에 대해 X의 이진 표현이 주어진 S의 부분 문자열인 경우에만 참이라고 말해야 합니다. 따라서 S ="0110 "이고 N =3이면 1, 10, 11이 모두 0110에 있으므로 결과가 참이 됩니다.

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

• n을 입력으로 사용하는 convert() 메서드를 정의합니다.

• ret :=빈 문자열

• n이 0이 아닌 동안

  • ret :=ret n mod 2 연결

  • n :=n / 2

• 역방향 ret 및 return

• 기본 방법에서 다음을 수행하십시오.

• i :=N의 경우 i>=N/2일 때 i를 1만큼 감소

  • 임시 :=변환(i)

  • temp가 S에 없으면 false를 반환합니다.

• true를 반환합니다.

이해를 돕기 위해 다음 구현을 살펴보겠습니다. −

예

#include <bits/stdc++.h>
using namespace std;
class Solution {
   public:
   string convert(int n){
      string ret = "";
      while(n){
         ret += (n % 2) + '0';
         n /= 2;
      }
      reverse(ret.begin(), ret.end());
      return ret;
   }
   bool queryString(string S, int N) {
      for(int i = N; i >= N/2; i-- ){
         string temp = convert(i);
         if(S.find(temp) == string::npos) return false;
      }
      return true;
   }
};
main(){
   Solution ob;
   cout << (ob.queryString("0110", 3));
}

입력

"0110"
3

출력

1