0%

LeetCode 1461. Check If a String Contains All Binary Codes of Size K

Posted on Edited on In

题目

原题在此

解析

只要关注最长的子串就好, 如果有最长的子串, 那较短的子串也一定在里面. 将子串放入set中, 最后比对size.

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
public:
    bool hasAllCodes(string s, int k) {
        int d = 0;
        unordered_set<int> hset;
        for (int i = 0; i < s.length(); i++) {
            d = (d << 1) | (s[i] - '0');
            if (i >= k - 1) {
                hset.insert(d);
                d -= (s[i - (k - 1)] - '0') << (k - 1);
            }
        }
        return hset.size() == (1 << k);
    }
};