สตริงไบนารีที่มีสตริงย่อยแทน 1 ถึง N ใน C ++

สมมติว่าเรามีสตริงไบนารี S และจำนวนเต็มบวก N เราต้องบอกว่าจริงก็ต่อเมื่อสำหรับทุกจำนวนเต็ม X ตั้งแต่ 1 ถึง N การแทนค่าไบนารีของ X เป็นสตริงย่อยของ S ที่กำหนด ดังนั้นหาก S =“0110 ” และ N =3 ผลลัพธ์จะเป็นจริง เนื่องจาก 1, 10 และ 11 ทั้งหมดมีอยู่ใน 0110

เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -

• กำหนดวิธีการแปลง () ที่จะใช้ n เป็นอินพุต

• ret :=สตริงว่าง

• ในขณะที่ n ไม่ใช่ 0

  • ret :=ret concatenate n mod 2

  • n :=n / 2

• ย้อนกลับและย้อนกลับ

• จากวิธีหลัก ให้ทำดังนี้

• สำหรับ i :=N, เมื่อ i>=N/2, ลด i ลง 1

  • อุณหภูมิ :=แปลง (i)

  • ถ้าอุณหภูมิไม่อยู่ใน S ให้คืนค่าเท็จ

• คืนค่าเป็นจริง

ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น -

ตัวอย่าง

#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