1461. Check If a String Contains All Binary Codes of Size K

leetcode medium

#array#csharp#leetcode#medium#sliding-window#string#tree

Task

Дана бинарная строка s и целое число k, верните true, если каждый бинарный код длины k является подстрокой s. В противном случае верните false.

Пример:

Input: s = "00110110", k = 2

Output: true

Explanation: The binary codes of length 2 are "00", "01", "10" and "11". They can be all found as substrings at indices 0, 1, 3 and 2 respectively.

C# solution

matched/original

public class Solution {
    public bool HasAllCodes(string s, int k) {
        int need = 1 << k;
        bool[] got = new bool[need];
        int allOne = need - 1;
        int hashVal = 0;
        
        for (int i = 0; i < s.Length; i++) {
            hashVal = ((hashVal << 1) & allOne) | (s[i] - '0');
            if (i >= k - 1 && !got[hashVal]) {
                got[hashVal] = true;
                need--;
                if (need == 0) {
                    return true;
                }
            }
        }
        return false;
    }
}

C++ solution

auto-draft, review before submit

#include <bits/stdc++.h>
using namespace std;

// Auto-generated C++ draft from the C# solution. Review containers, LINQ and helper types before submit.
class Solution {
public:
    public bool HasAllCodes(string s, int k) {
        int need = 1 << k;
        bool[] got = new bool[need];
        int allOne = need - 1;
        int hashVal = 0;
        
        for (int i = 0; i < s.size(); i++) {
            hashVal = ((hashVal << 1) & allOne) | (s[i] - '0');
            if (i >= k - 1 && !got[hashVal]) {
                got[hashVal] = true;
                need--;
                if (need == 0) {
                    return true;
                }
            }
        }
        return false;
    }
}

Java solution

matched/original

class Solution {
    public static boolean hasAllCodes(String s, int k) {
        int need = 1 << k;
        boolean[] got = new boolean[need];
        int allOne = need - 1;
        int hashVal = 0;

        for (int i = 0; i < s.length(); i++) {
            hashVal = ((hashVal << 1) & allOne) | (s.charAt(i) - '0');
            if (i >= k - 1 && !got[hashVal]) {
                got[hashVal] = true;
                need--;
                if (need == 0) {
                    return true;
                }
            }
        }
        return false;
    }
}

Go solution

matched/original

func hasAllCodes(s string, k int) bool {
    need := 1 << k
    got := make([]bool, need)
    allOne := need - 1
    hashVal := 0
    
    for i := 0; i < len(s); i++ {
        hashVal = ((hashVal << 1) & allOne) | int(s[i]-'0')
        if i >= k-1 && !got[hashVal] {
            got[hashVal] = true
            need--
            if need == 0 {
                return true
            }
        }
    }
    return false
}

Explanation

Algorithm

Определите количество возможных двоичных кодов длины k.

Создайте массив для отслеживания, какие коды были найдены. Итерируйте по строке s, вычисляя хэш для текущего окна длины k и обновляя массив отслеживания.

Возвращайте true, если все возможные коды найдены, иначе false.

😎