[LeetCode：Check If a String Contains All Binary Codes of Size K] | 刷题打卡

真心求大家关注和点赞，原创不易，你们的支持是我写作的最大动力！

题目描述

给你一个只包括二进制数的字符串 s 和整数 k，如果每个长度为 k 的二进制串都是 s 的字串（substring）返回 true，否则返回 false（注意：substring 和 subsequence 的区别）

例一：

输入: s = "00110110", k = 2
输出: true
解释: 长度为 2 的二进制串都有："00", "01", "10" 和 "11". 他们都是 s 的字串

例二：

输入: s = "00110", k = 2
输出: true

例三：

输入: s = "0110", k = 1
输出: true
解释: 长度为 1 的二进制串只有："0" 和 "1", 他们也都是 s 的字串 

例四：

输入: s = "0110", k = 2
输出: false
解释: 长度为 2 的二进制串 "00" 不是 s 的字串（但是是子序列）

例五：

输入: s = "0000000001011100", k = 4
输出: false

思路分析

题目很短也很好理解，看完后思路应该很快就有了：先求所有长度为 k 的二进制串，然后判断所有的二进制串是不是都是 s 的字串。

解题前需要明确的问题也很清晰：

1. 如何求所有长度为 k 的二进制串
2. 如何判断字符串是否是另一个串的字串

问题一：如何求所有长度为 k 的二进制串

不用多想，一定是个回溯问题！长度为 k 的字符串的每一位都有 0 和 1 两种填充可能，一共有 $2^k$2k 种结果。写出如下回溯代码：

const getBinaryCodes = (n) => {
  const result = []; // 保存最终结果
  const base = [0, 1]; // 待选集合只有 0 和 1
  const backtrace = (len, cur) => {
    if (len === 0) {
      // 长度为 0 表示找到一个目标串
      result.push(cur);
      return;
    }
    for (let i = 0; i < base.length; i++) {
      // 对于每个 cur，都分别拼接 0 和 1
      backtrace(len - 1, `${cur}${base[i]}`);
    }
  };
  // 初始条件长度为 n，cur 为空字符串
  backtrace(n, "");
  return result;
};

问题二：如何判断字符串是否是另一个串的字串

我用了一种取巧偷懒的方式，使用 ES String 原型对象的 includes 方法来判断...（别骂我...） ，最后用数组原型方法 every 去判断是不是每个字串都是 s 的字串。虽然能 AC，但是非常非常耗时！

这个时候我又把问题抛给了学会计的女朋友，一通题目说明后，她说可以先把字符串 s 的所有长度为 k 的字串都找到，然后判断个数是否等于 2 的 k 次方就可以了呀！

Ohhhhhhh!

瞬间感觉费半天劲儿写回溯，判断字串是否是字串的我好蠢，被秒的渣都不剩。

AC 代码

var hasAllCodes = function (s, k) {
  const set = new Set();
  for (let i = 0; i <= s.length - k; i++) {
    set.add(s.substr(i, k));
    if (set.size === Math.pow(2, k)) {
      return true;
    }
  }
  return false;
};

总结

题目中有些特殊条件一定是可以帮你优化时间复杂度的，比如这道题中的待选字串只有 0 和 1，再比如：Remove Palindromic Subsequences 中的字串只限制为 a 和 b，再再再比如有序的数字序列的查找用二分法，再再再再比如求最值的动态规划，等等这些信号都在告诉你，别用蛮力，这道题有迹可循！

本文正在参与「掘金 2021 春招闯关活动」, 点击查看 活动详情