子串能表示从 1 到 N 数字的二进制串【LC1016】
给定一个二进制字符串 s 和一个正整数 n，如果对于 [1, n] 范围内的每个整数，其二进制表示都是 s 的 子字符串 ，就返回true，否则返回 false 。
子字符串 是字符串中连续的字符序列。
把智齿了，今天稍微休息一下
正向+枚举
- 思路
枚举1至n的每一个数的二进制表示是否在s中出现，如果所有二进制表示都出现，那么返回true；如果有一个不出现，则返回false - 实现
class Solution { public boolean queryString(String s, int n) { for (int i = 1; i <= n; i++){ if (s.indexOf(Integer.toBinaryString(i)) == -1){ return false; } } return true; } }
复杂度
- 时间复杂度：O(min(m,n)∗mlogmin(m,n)),m为s的长度
- 空间复杂度：O(logn)
逆向+哈希表
- 思路枚举s的每一个子串（首字符不为0），如果其数值小于等于n，那么将其数值记录在哈希表中，如果最后哈希表中的个数等于n，那么返回true
- 如何将子串转化为二进制数？
设当前得到的二进制数为x，且下一个字符s[j+1]为c，那么将x那么将 x xx 更新为 (x << 1) | (c - '0')
实现
class Solution { public boolean queryString(String S, int n) { var seen = new HashSet<Integer>(); var s = S.toCharArray(); for (int i = 0, m = s.length; i < m; ++i) { int x = s[i] - '0'; if (x == 0) continue; // 二进制数从 1 开始 for (int j = i + 1; x <= n; j++) { seen.add(x); if (j == m) break; x = (x << 1) | (s[j] - '0'); // 子串 [i,j] 的二进制数 } } return seen.size() == n; } } 作者：灵茶山艾府 链接：https://leetcode.cn/problems/binary-string-with-substrings-representing-1-to-n/solutions/2265097/san-chong-suan-fa-cong-bao-li-dao-you-hu-nmtq/ 来源：力扣（LeetCode） 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
复杂度
- 时间复杂度：O(mlogn),m为s的长度
- 空间复杂度：O(min(mlogn,n)),哈希表所需要的空间
