Задача: Дана строка состоящая из нулей и единиц, и целое число k
. Нужно проверить что каждое двоичное число длинной k
является подпоследовательностью строки.
Пример 1: Input: s = "00110110", k = 2 Output: true
Пример 2: Input: s = "0110", k = 1 Output: true
Огриничения:
1 <= s.length <= 5 * 10^5
1 <= k <= 20
Решение:
class Solution {
public:
bool hasAllCodes(string s, int k) {
const int count = 2 << (k - 1);
int m = 0;
if (count >= s.size())
return false;
for (unsigned int value = 0; value <= count; ++value)
{
bool flag = false;
for (size_t i = 0; i <= s.size() - k; ++i)
{
unsigned int current = toValue(s, i, k);
if (value == current)
{
++m;
if (m == count)
return true;
flag = true;
break;
}
}
if (!flag)
return false;
}
if (m == count)
return true;
return false;
}
unsigned int toValue(const string& s, size_t i, size_t k)
{
unsigned int value = 0;
for (int j = i; j < i + k; j++)
{
if (s[j] == '1')
value++;
value = value << 1;
}
value = value >> 1;
return value;
}
};
Как реализовать эффективнее?