오늘은 3월 리트코딩 챌린지 12번째 문제를 풀어보겠습니다.

문제 설명

이진 문자열 s와 정수 k가 주어집니다.

길이가 k인 모든 이진 코드가 s의 하위 문자열이면 True를 반환합니다. 그렇지 않으면 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)

여기에서 코드를 찾을 수 있습니다.

<사업부 클래스="ltag-github-body">

2021년 3월 LeetCoding Challenge에 대한 제 다른 게시물을 확인하세요.

<올>

March LeetCoding Challenge — Day 1 — Distribute Candies

March LeetCoding Challenge — Day 2 — Set Mismatch

March LeetCoding Challenge — Day 3 — Missing Number

March LeetCoding Challenge — Day 4 — Intersection of Two Linked Lists

March LeetCoding Challenge — Day 5 — Average of Levels in Binary Tree

March LeetCoding Challenge — Day 6 — Short Encoding of Words

March LeetCoding Challenge — Day 8 — Remove Palindromic Subsequences

March LeetCoding Challenge — Day 10 — Integer to Roman