题目描述

blablabla

样例

本质滑动窗口维护长度为k的窗口（区间），判断是否是2^k. （即二进制的位上数的表示。）

bool hasAllCodes(string s, int k) {
        unordered_set<string> seen;
        int len = min((int)s.length(), k);
        for (int i = 0; i <= s.length() - len ; i++)
            seen.insert(s.substr(i, len));
        return seen.size() == 1 << k;
    }

def hasAllCodes(self, s, k):
    return len({s[i:i + k] for i in range(len(s) - k + 1)}) == 2 ** k
    #或者位运算
    #return len({s[i - k : i] for i in range(k, len(s) + 1)}) == 1 << k

算法2

(滑动窗口遍历) $O(n)$

def hasAllCodes(self, s: str, k: int) -> bool:
        st = set()
        for i in range(k, len(s) + 1):
            st.add(s[i - k : i])
            if len(st) == 1 << k:
                break
        return len(st) == 1 << k