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

문제 링크

 

정답 코드

def solution(strs, t):
    word_set = set(strs)
    N = len(t)
    
    dp = [float('inf')] * (N + 1)
    dp[0] = 0
    
    t = '_' + t

    for idx in range(1, N + 1):
        for j in range(1, 6):
            if idx - j >= 0 and t[idx - j+1:idx+1] in word_set:
                dp[idx] = min(dp[idx], dp[idx - j] + 1)
    
    return dp[-1] if dp[-1] != float('inf') else -1