Сегодня мы решим 12-ю задачу мартовского LeetCoding Challenge.
Постановка задачи
Дана двоичная строка s и целое число k.
Возвратите True, если каждый двоичный код длины k является подстрокой s. В противном случае верните False.
Пример 1:
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.
Пример 2:
Input: s = "00110", k = 2 Output: true
Пример 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.
Пример 4:
Input: s = "0110", k = 2 Output: false Explanation: The binary code "00" is of length 2 and doesn't exist in the array.
Пример 5:
Input: s = "0000000001011100", k = 4 Output: false
Решение
В этой задаче нас просят найти, есть ли у нас все двоичные коды размера k в заданной строке.
Мы знаем, что для данного размера k всего может быть 2^k чисел. Нам нужно проверить, присутствуют ли все эти 2^k чисел в данной строке. Для этого мы можем использовать HashSet для хранения всех значений, которые мы обнаружили. В конце концов, мы можем сравнить размер HashSet и 2^k , если они равны, то вернуть true, иначе вернуть false.
Код приведен ниже.
Временная сложность: O(n)
Космическая сложность: O(n)
Код можно найти здесь
Ознакомьтесь с другими моими сообщениями о мартовском конкурсе LeetCoding Challenge 2021.
- Мартовское соревнование LeetCoding — День 1 — Раздача конфет
- Мартовский вызов LeetCoding — День 2 — Набор несоответствий
- Мартовский вызов LeetCoding — день 3 — пропущенный номер
- Мартовский вызов LeetCoding — День 4 — Пересечение двух связанных списков
- Мартовское соревнование LeetCoding — День 5 — Среднее количество уровней в двоичном дереве
- Мартовский вызов LeetCoding — День 6 — Короткое кодирование слов
- Мартовское соревнование LeetCoding — День 8 — Удаление палиндромных последовательностей
- Мартовский вызов LeetCoding — День 10 — Целое число в числовое число
