1461. Check If a String Contains All Binary Codes
Question
Given a binary string
s
and an integerk
, returntrue
if every binary code of lengthk
is a substring ofs
. Otherwise, returnfalse
.
Solution
位运算+哈希表,用整数num记录二进制编码并加入哈希表中。
首先将字符串内的前k位二进制码转换为整数。并将其数值添加到哈希表内。
滑动窗口遍历,维持num为k长度内二进制码所对应的整数,并在遍历时将num加入哈希集合。
如果哈希集合的size达到k长度对应的可组合数,则返回true,否则返回false。
位运算与掩码
为了维护整数num,首先将其二进制编码向左移动一位。
然后与mask进行按位与运算,屏蔽掉多余的位数。
mask的值为k长度对应的可组合数-1。
Code
1 | class Solution { |