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

LeetCode medium original: C# #array #csharp #leetcode #medium #sliding-window #string #tree
Il testo del problema è tradotto dal russo per la lingua selezionata. Il codice resta invariato.
LeetCode Static

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

Esempio:

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# soluzione

abbinato/originale 
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++ soluzione

bozza automatica, rivedere prima dell'invio 
#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 soluzione

abbinato/originale 
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 soluzione

abbinato/originale 
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
}

Algorithm

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

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

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

😎

Vacancies for this task

offerte attive with overlapping task tags are mostrati.

Tutte le offerte
Non ci sono ancora offerte attive.