Halo

A magic place for coding

0%

LeetCode解题报告(315)-- 1461. Check If a String Contains All Binary Codes of Size K

Problem

Given a binary string s and an integer k.

Return True if every binary code of length k is a substring of s. Otherwise, return False.

Example 1:

1
2
3
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:

1
2
Input: s = "00110", k = 2
Output: true

Example 3:

1
2
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:

1
2
3
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:

1
2
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

Analysis

  题目给了一个字符串s,还有一个数值k,问长度为k的二进制串是否都是s 的子串。这道题目要求解并不困难,最暴力的方法是把长度为k的二进制串都求出来,然后一个一个在s中进行对比,如果有一个不符合则return false,如果全部都能在s中找到,则return true。

  但是这种做法有性能的问题。把长度为k的二进制串都算出来本身就要有一定的计算量,同时,还需要在s中寻找是否有匹配的子串,这种find()操作在性能上是很低的。我们能否有一种更加高效的做法呢?

   不妨逆向思考,我们不在s中找匹配的子串,而是从s中找出所有满足长度的子串,看看这些子串是否就是所有长度为k的二进制串。因为长度为k的二进制串的数量是$2^k$个,所以我们只需要在s 中提取出所有长度为k的字符串,放到一个集合中,如果集合中元素的个数是$2^k$,说明能够构成;否则不能。


Solution

  无。


Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
public:
bool hasAllCodes(string s, int k) {
unordered_set<string> dict;
for (int i = 0; i + k <= s.size(); i++) {
string temp = s.substr(i, k);
dict.insert(temp);
}

if (dict.size() == pow(2, k)) {
return true;
}
return false;
}
};

Summary

  这道题目本身难度不大,是借助了set这个数据结构做了一些优化。这道题目的分享到这里,感谢你的支持!

Welcome to my other publishing channels