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

class Solution:
    def hasAllCodes(self, s: str, k: int) -> bool:
        ss = {s[i : i + k] for i in range(len(s) - k + 1)}
        return len(ss) == 1 << k

class Solution {
    public boolean hasAllCodes(String s, int k) {
        Set<String> ss = new HashSet<>();
        for (int i = 0; i < s.length() - k + 1; ++i) {
            ss.add(s.substring(i, i + k));
        }
        return ss.size() == 1 << k;
    }
}

class Solution {
public:
    bool hasAllCodes(string s, int k) {
        unordered_set<string> ss;
        for (int i = 0; i + k <= s.size(); ++i) {
            ss.insert(move(s.substr(i, k)));
        }
        return ss.size() == 1 << k;
    }
};

func hasAllCodes(s string, k int) bool {
	ss := map[string]bool{}
	for i := 0; i+k <= len(s); i++ {
		ss[s[i:i+k]] = true
	}
	return len(ss) == 1<<k
}

class Solution:
    def hasAllCodes(self, s: str, k: int) -> bool:
        if len(s) - k + 1 < (1 << k):
            return False
        vis = [False] * (1 << k)
        num = int(s[:k], 2)
        vis[num] = True
        for i in range(k, len(s)):
            a = (ord(s[i - k]) - ord('0')) << (k - 1)
            b = ord(s[i]) - ord('0')
            num = ((num - a) << 1) + b
            vis[num] = True
        return all(v for v in vis)

class Solution {
    public boolean hasAllCodes(String s, int k) {
        int n = s.length();
        if (n - k + 1 < (1 << k)) {
            return false;
        }
        boolean[] vis = new boolean[1 << k];
        int num = Integer.parseInt(s.substring(0, k), 2);
        vis[num] = true;
        for (int i = k; i < n; ++i) {
            int a = (s.charAt(i - k) - '0') << (k - 1);
            int b = s.charAt(i) - '0';
            num = (num - a) << 1 | b;
            vis[num] = true;
        }
        for (boolean v : vis) {
            if (!v) {
                return false;
            }
        }
        return true;
    }
}

class Solution {
public:
    bool hasAllCodes(string s, int k) {
        int n = s.size();
        if (n - k + 1 < (1 << k)) return false;
        vector<bool> vis(1 << k);
        int num = stoi(s.substr(0, k), nullptr, 2);
        vis[num] = true;
        for (int i = k; i < n; ++i) {
            int a = (s[i - k] - '0') << (k - 1);
            int b = s[i] - '0';
            num = (num - a) << 1 | b;
            vis[num] = true;
        }
        for (bool v : vis)
            if (!v) return false;
        return true;
    }
};

func hasAllCodes(s string, k int) bool {
	n := len(s)
	if n-k+1 < (1 << k) {
		return false
	}
	vis := make([]bool, 1<<k)
	num := 0
	for i := 0; i < k; i++ {
		num = num<<1 | int(s[i]-'0')
	}
	vis[num] = true
	for i := k; i < n; i++ {
		a := int(s[i-k]-'0') << (k - 1)
		num = (num-a)<<1 | int(s[i]-'0')
		vis[num] = true
	}
	for _, v := range vis {
		if !v {
			return false
		}
	}
	return true
}