[프로그래머스] 단어 퍼즐

😀요점

1. DP를 통해서 시간을 단축해야한다.

😎풀이

function solution(strs, t) {
    const dp = Array(t.length + 1).fill(Infinity); // DP 테이블 초기화
    dp[0] = 0; // 시작점 초기화

    for (let i = 1; i <= t.length; i++) { // t의 각 문자에 대해 반복
        for (let j = 0; j < strs.length; j++) { // 주어진 단어 조각들에 대해 반복
            const str = strs[j]; // 현재 단어 조각
            const len = str.length; // 현재 단어 조각의 길이
            if (i >= len && t.substring(i - len, i) === str) { // t의 부분 문자열이 현재 단어 조각과 일치하는 경우
                dp[i] = Math.min(dp[i], dp[i - len] + 1); // 최소 개수 갱신
            }
        }
    }

    return dp[t.length] === Infinity ? -1 : dp[t.length]; // 결과 반환
}