[LeetCode] 717. 1-bit and 2-bit Characters

😎풀이

마지막 문자가 1비트 문자인지 여부 반환, 여기서 1비트 문자란 0만을 의미함

1. binary: 가능한 decode bit 목록
2. 백트레킹 수행
   2-1. 남은 비트가 한 자리 수 이고, 그 비트가 0이라면 문제에서 원하는 조건을 충족하므로 true 반환
   2-2. isDecodable: binary를 순회하며 해당 데이터를 통해 bit를 decode 할 수 있는지 여부
   2-3. curBinary로 현재 bit를 decode할 수 있다면 재귀적으로 탐색, 아니라면 다음 탐색 시작
   2-4. 가능한 binary 목록에서 decode할 수 없다는 것이므로 false 반환
3. bits를 backTracking하여 문제 조건에 충족한다면 true, 아니라면 false 반환

function isOneBitCharacter(bits: number[]): boolean {
    const binary = [[0], [1, 0], [1, 1]]
    function backTracking(remainBits: number[]) {
        if(remainBits.length === 1 && remainBits[0] === 0) return true
        let isDecodable = true
        for(const curBinary of binary) {
            for(let i = 0; i < curBinary.length; i++) {
                if(curBinary[i] === remainBits[i]) continue
                isDecodable = false
                break 
            }
            if(!isDecodable) {
                isDecodable = true
                continue
            }
            if(backTracking(remainBits.slice(curBinary.length))) return true
        }
        return false
    }
    return backTracking(bits)
};