[LeetCode] 1016. Binary String With Substrings Representing 1 To N

[grandyang]

Given a binary string S (a string consisting only of '0' and '1's) and a positive integer N, return true if and only if for every integer X from 1 to N, the binary representation of X is a substring of S.

Example 1:

Input: S = "0110", N = 3
Output: true

Example 2:

Input: S = "0110", N = 4
Output: false

Note:

1. 1 <= S.length <= 1000
2. 1 <= N <= 10^9

这道题给了一个二进制的字符串S，和一个正整数N，问从1到N的所有整数的二进制数的字符串是否都是S的子串。没啥说的，直接上最简单粗暴的解法，验证从N到1之间所有的数字，先求出其二进制数的字符串，在 C++ 中可以利用 bitset 来做，将其转为字符串即可。由于定义了 32 位的 bitset，转为字符串后可能会有许多 leading zeros，所以首先要移除这些0，通过在字符串中查找第一个1，然后通过取子串的函数就可以去除所有的起始0了。然后在S中查找是否存在这个二进制字符串，若不存在，直接返回 false，遍历完成后返回 true 即可，参见代码如下：

class Solution {
public:
    bool queryString(string S, int N) {
        for (int i = N; i > 0; --i) {
            string b = bitset<32>(i).to_string();
            if (S.find(b.substr(b.find("1"))) == string::npos) return false;
        }
        return true;
    }
};

Github 同步地址:

#1016

参考资料：

https://leetcode.com/problems/binary-string-with-substrings-representing-1-to-n/

https://leetcode.com/problems/binary-string-with-substrings-representing-1-to-n/discuss/260847/JavaC%2B%2BPython-O(S)

https://leetcode.com/problems/binary-string-with-substrings-representing-1-to-n/discuss/260882/C%2B%2B-O(S-log-N)-vs.-O(N-*-(S-%2B-log-N))

LeetCode All in One 题目讲解汇总(持续更新中...)