Check If a String Contains All Binary Codes of Size K

https://leetcode.com/problems/check-if-a-string-contains-all-binary-codes-of-size-k/

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

s = "00110110", k = 2 -> true

 

set + dfs

class Solution:
    def hasAllCodes(self, s: str, k: int) -> bool:
        if len(s) < k:
            return False
        
        candidates = set()
        
        for i in range(0, len(s)-k+1):
            candidates.add(s[i:i+k])
        
        def dfs(n, cur=''):
            if n == 0:
                return cur in candidates
            
            left = cur + '0'
            right = cur + '1'
            
            return dfs(n-1, left) and dfs(n-1, right)
        
        return dfs(k)

 

better solution

class Solution:
    def hasAllCodes(self, s: str, k: int) -> bool:
        if len(s) < k - 1 + 2 ** k:
            return False
        remaining = 2 ** k
        exist = set()
        for i in range(len(s) - k, -1, -1):
            if s[i:(i + k)] not in exist:
                remaining -= 1
                exist.add(s[i:(i + k)])
            if i < remaining:
                return False
            if remaining == 0:
                return True