题目描述

给你一个二进制字符串 s 和一个整数 k 。

如果所有长度为 k 的二进制字符串都是 s 的子串，请返回 True ，否则请返回 False 。

样例

样例1

输入：s = "00110110", k = 2
输出：true
解释：长度为 2 的二进制串包括 "00"，"01"，"10" 和 "11"。
它们分别是 s 中下标为 0，1，3，2 开始的长度为 2 的子串。

样例2

输入：s = "00110", k = 2
输出：true

样例3

输入：s = "0110", k = 2
输出：false
解释：长度为 2 的二进制串 "00" 没有出现在 s 中。

算法一

思路

枚举字符串s的所有长度为K的子串，加入到集合中去

最后判断集合中的元素数量是否等于所有长度为k的二进制串枚

细节

枚举长度为k的子串，用滑动窗口即可

这里把01字符串转化为 int 来存储

若窗口长度满足k，每次向前滑动的时候减去窗口最左边的一位即可

复杂度

时间 : $0(n)$

空间 : $0(2^k)$ 一个集合来存其长度为K的子串

c++代码

class Solution {
public:
    bool hasAllCodes(string s, int k) {
        unordered_set<int> S; 
        // 把01串 转化为 int 整数  类似于双指针
        for (int i = 0, w = 0; i < s.size(); i ++ ) {
            w = w * 2 + s[i] - '0';
            // 超过k个了 ， 然后滑动一位
            if (i >= k) w -= s[i - k] - '0' << k;
            if (i >= k - 1) S.insert(w);
        }
        return S.size() == (1 << k);
    }
};

算法2

思路

用全排列枚举出所有长度为K的二进制子串，存到集合S中去；

枚举字符串s所有的长度为K的子串，不放设为sub_s。如果其存在于集合s, 则将其在集合中删去。

如果都存在，那么集合s最后的大小为0，判断其大小即可。

注意 ： TLE 过了146 / 196 个样例 权当练习全排列dfs

复杂度

时间 ： $0(k! + n)$ 枚举所有长度为k的2进制的子串 + 遍历字符串

空间 ： $0(2^k)$ 一个集合来存其长度为K的子串

c++ 代码

class Solution {
     set<int> Set;
public:
    bool hasAllCodes(string s, int k) {
        int  str = 0;
        dfs(0, k, str);
        for(int i = 0, w = 0; i < s.size(); i++)
        {
            w = w * 2 + s[i] - '0';
            if(i >= k) 
                w -= s[i - k] - '0' << k;  // 记得左移K 
            if(i >= k - 1 && Set.count(w))
                 Set.erase(w);
        }
        return Set.empty();
    }

    void dfs(int u, int k, int str){   
    if(u == k)
    {
        Set.insert(str);
        return;
    }
    dfs(u + 1, k, str * 2 + 0);
    dfs(u + 1, k, str * 2 + 1); 
    }
};