leetcode 1461. 检查一个字符串是否包含所有长度为 K 的二进制子串

6个月前更新

1461. 检查一个字符串是否包含所有长度为 K 的二进制子串

法一：使用unordered_set ，通过集合数量来判断

class Solution { public: bool hasAllCodes(string s, int k) { int size = s.size(); int k_2kFang = pow(2,k); if(size - k + 1 < k_2kFang)  return false;//如果长度为k的子串数量比2^k还少，说明就算所有子串符合条件也不囊括所有的长度为k的二进制
 unordered_set<int> nums; int now = 0, mult = 1; for(int i = 0;i < k;i++){ if(s[k-1-i] == '1')  now += mult; mult *= 2; } nums.insert(now);//先计算前k个字符所代表的数，放入到集合中

        for(int i = 1;i <= size - k;i++){ if(s[i-1] == '1')  now -= k_2kFang/2;//如果将要移走的位置是1，那么就要减掉它所代表的2^(k-1)
            now *= 2;//代表二进制数整体左移。比如 0 1 1 1 (7)，左移后就是 1 1 1 0 (14)
            if(s[i+k-1] == '1')  now++;  //如果新进来的数字是1，那么now增加1
 nums.insert(now); if(nums.size() == k_2kFang)  return true; } return nums.size() == k_2kFang; } };