WordPuzzle

[dlehdanakf]

단어퍼즐

• 문제 바로가기
• 주어진 퍼즐조각을 활용하여 특정 단어를 최소한의 조각을 사용하여 만드는 방법을 구하는 문제.
• DFS 방식으로 문제를 해결하려 했지만 시간초과 + 스택오버플로우 크리 맞고 100점만점에 43점밖에 얻지 못했다...
• 해설을 찾아봤더니 DP를 활용한다고 한다.

function solution(strs, t) {
    let answer = -1;
    const traverse = (s, i) => {
        if(s.length === 0) {
            answer = i;
            return;
        }
        if(answer !== -1 && i >= answer) {
            return;
        }

        const candidates = strs.filter(e => s.indexOf(e) === 0);
        for(const c of candidates) {
            traverse(s.substring(c.length), i + 1);
        }
    };

    traverse(t, 0);
    return answer;
}