Given a binary string s
and an integer k
.
Return True if any binary code of length k
is a substring of s
. Otherwise, return False.
Example 1:
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 indicies 0, 1, 3 and 2 respectively.
Example 2:
Input: s = "00110", k = 2 Output: true
Example 3:
Input: s = "0110", k = 1 Output: true Explanation: The binary codes of length 1 are "0" and "1", it is clear that both exist as a substring.
Example 4:
Input: s = "0110", k = 2 Output: false Explanation: The binary code "00" is of length 2 and doesn't exist in the array.
Example 5:
Input: s = "0000000001011100", k = 4 Output: false
Constraints:
1 <= s.length <= 5 * 10^5
s
consists of 0’s and 1’s only.1 <= k <= 20
Solution: Hashtable
Insert all possible substrings into a hashtable, the size of the hashtable should be 2^k.
Time complexity: O(n*k)
Space complexity: O(2^k*k) -> O(2^k)
std::string_view: 484 ms, 40.1MB
std::string 644 ms, 58.6MB
C++
1 2 3 4 5 6 7 8 9 10 11 12 13 14 |
// Author: Huahua // std::string_view: 468 ms, 37.3MB // std::string: 636 ms, 58.6MB class Solution { public: bool hasAllCodes(string_view s, int k) { const int n = s.length(); if ((n - k + 1) * k < (1 << k)) return false; unordered_set<string_view> c; for (int i = 0; i + k <= n; ++i) c.insert(s.substr(i, k)); return c.size() == (1 << k); } }; |