題目

給你一個二進位制字串 s 和一個整數 k 。

如果所有長度為 k 的二進位制字串都是 s 的子串，請返回 True ，否則請返回 False 。

示例 1：輸入：s = "00110110", k = 2 輸出：true

解釋：長度為 2 的二進位制串包括 "00"，"01"，"10" 和 "11"。

它們分別是 s 中下標為 0，1，3，2 開始的長度為 2 的子串。

示例 2：輸入：s = "00110", k = 2 輸出：true

示例 3：輸入：s = "0110", k = 1 輸出：true

解釋：長度為 1 的二進位制串包括 "0" 和 "1"，顯然它們都是 s 的子串。

示例 4：輸入：s = "0110", k = 2 輸出：false

解釋：長度為 2 的二進位制串 "00" 沒有出現在 s 中。

示例 5：輸入：s = "0000000001011100", k = 4 輸出：false

提示：1 <= s.length <= 5 * 10^5

s 中只含 0 和 1 。

1 <= k <= 20

解題思路分析

1、雜湊輔助；時間複雜度O(n)，空間複雜度O(2^n)

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

2、陣列輔助；時間複雜度O(n)，空間複雜度O(2^n)

func hasAllCodes(s string, k int) bool {	length := 1 << k	arr := make([]bool, length)	cur := 0	for i := 0; i < len(s); i++ {		num := int(s[i] - '0')		cur = cur<<1 + num		if i >= k-1 {			cur = cur & (length - 1)			arr[cur] = true		}	}	for i := 0; i < len(arr); i++ {		if arr[i] == false {			return false		}	}	return true}

總結

Medium題目，藉助陣列或者map來統計，然後判斷