Binary String With Substrings Representing 1 To N ใน C++

คำอธิบายปัญหา

กำหนดสตริงไบนารี S และจำนวนเต็มบวก N ต้องการตรวจสอบว่าสำหรับทุกจำนวนเต็ม X จาก 1 ถึง N การแทนค่าในฐานสองของ X เป็น substring ของ S หรือไม่

ตัวอย่าง: S="0110", N=3 → true (1="1", 2="10", 3="11" ทั้งหมดอยู่ใน "0110")

ข้อสังเกตสำคัญ

ไม่จำเป็นต้องตรวจสอบทุกตัวเลข 1 ถึง N เพียงพอที่จะตรวจสอบ N/2 ถึง N เท่านั้น เพราะถ้าตัวเลขใหญ่ๆ อยู่ใน S ตัวเลขเล็กๆ ที่เป็น prefix ก็จะอยู่ใน S อัตโนมัติ

ตัวอย่างโค้ด C++

#include <bits/stdc++.h>
using namespace std;

class Solution {
public:
    string convert(int n) {
        string ret = "";
        while(n > 0) {
            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;
    }
};

int main() {
    Solution ob;
    cout << ob.queryString("0110", 3);
    return 0;
}

อินพุต

"0110" 3

เอาต์พุต

1