Binary String With Substrings Representing 1 To N trong C++

Cho chuỗi nhị phân S và số nguyên dương N, kiểm tra xem với mọi số X từ 1 đến N, biểu diễn nhị phân của X có phải là substring của S hay không. Ví dụ: S = "0110", N = 3, kết quả true vì "1", "10", "11" đều có trong "0110".

Giải pháp tối ưu: chỉ cần kiểm tra từ N đến N/2 (vì các số nhỏ hơn sẽ tự động là substring của các số lớn hơn nếu số lớn có mặt).

• Hàm convert(n): chuyển n sang nhị phân (chia 2 lặp, đảo chuỗi)

• Với i từ N giảm đến N/2:
  temp := convert(i)
  Nếu temp không có trong S: return false

• Trả về true

Ví dụ

#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;    } }; int main(){    Solution ob;    cout << (ob.queryString("0110", 3)); }

Đầu vào

"0110" 3

Đầu ra

1