[LeetCode] 756. Pyramid Transition Matrix

😎풀이

1. allowed를 통해 생성 가능한 피라미드 형태 구축
2. 빠른 가지치기를 위한 캐시 Set 구축
3. DFS를 통해 상위 루트를 재귀적으로 구축하며 검증
4. bottom을 통해 최상위 층까지 구축 가능한지에 대한 여부 반환

function pyramidTransition(bottom: string, allowed: string[]): boolean {
    const map = new Map<string, string[]>()
    for(const [a, b, c] of allowed) {
        const key = a + b
        map.set(key, [...(map.get(key) ?? []), c])
    }
    const seen = new Set<string>()
    function buildNext(curLine: string) {
        if(curLine.length === 1) return true
        if(seen.has(curLine)) return false
        function buildCurr(i: number, nextLine: string) {
            if(i === curLine.length - 1) return buildNext(nextLine)
            const key = curLine[i] + curLine[i + 1]
            const candidates = map.get(key)
            if(!candidates) return false
            return candidates.some(char => buildCurr(i + 1, nextLine + char))
        }
        if(buildCurr(0, "")) return true
        seen.add(curLine)
        return false
    }
    return buildNext(bottom)
};