1461. Check If a String Contains All Binary Codes of Size K 문제 풀이

1461. Check If a String Contains All Binary Codes of Size K

난이도: Medium

---

Given a binary string s and an integer k, return true if every binary code of length k is a substring of s. Otherwise, return false.

 

Example 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 indices 0, 1, 3 and 2 respectively.

Example 2:

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. 

Example 3:

Input: s = "0110", k = 2
Output: false
Explanation: The binary code "00" is of length 2 and does not exist in the array.

 

Constraints:

• 1 <= s.length <= 5 * 105
• s[i] is either '0' or '1'.
• 1 <= k <= 20

문제 설명

문자열 s와 정수 k가 주어질 때, 길이가 k인 모든 이진 코드가 s의 부분 문자열이면 true를 리턴하고 아니면 false를 리턴하는 문제이다. 

 

문제 접근법

길이가 k인 이진코드를 모두 구하고 나서 문자열 s에 부분 문자열인지 체크 

 

코드

 

/**
 * @param {string} s
 * @param {number} k
 * @return {boolean}
 */
var hasAllCodes = function(s, k) {
    const binaryCodes = [] 
    const tmp = Array.from({length:k},()=>0)
    const getCodes = (l)=>{
        if(l === k){
            binaryCodes.push(tmp.join('').slice())
        }else{
            for(let k=0; k<2; k++){
                tmp[l] = k 
                getCodes(l+1)
            }
        }
    }
    getCodes(0)
    for(let i=0; i<binaryCodes.length; i++){
        const regex = new RegExp(binaryCodes[i])
        if(!regex.test(s)) return false 
    }
    return true

    };

문제점

결과는 시간 초과!! 😂😂😂😂

아무래도 길이가 k 인 이진 코드를 모두 구하는 과정에서 시간 초과가 뜬 거 같습니다.

 

개선한 코드 

문제의 힌트를 보고 나서 아주 간단한 문제인 걸 알았습니다!!

길이가 k인 모든 이진코드의 수는  결국 2 ^ k 개수와 같기 때문에 문자열 s를 k길이만큼 잘라 set에 저장하여 길이를 비교하면 되는 문제였습니다..!

 

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