def solution(strs, t):
DP = [0] * ((n := len(t)) + 1)
for i in range(1, n+1) :
DP[i] = min((DP[k] + 1 for k in range(max(0, i - 5), i) if t[k:i] in strs), default = 1e6)
return DP[-1] if DP[-1] < 1e6 else -1
알고리즘
편집거리 와 비슷한문제
DP[i] : t[:i+1] 을 만들기 위해 사용되는 최소 단어 수
DP[i] = min(DP[k] + 1), where max(0, i-5) <= k < i
strs의 원소 최대길이는 5 이기 때문에 t[k:i]의 길이가 5이하인 경우에만 기존의 t[:k]에 새로운 단어조각 하나를 추가해 t[:i] 를 완성 시킬 수 있다.
t[:i+1]단어 끝에서부터 최대 5개까지만 검사를 해서t[k:i+1]가 있는 단어조각이면DP를 최신화 시켜준다.
이런식으로
def solution(strs, t):
DP = [0] * ((n := len(t)) + 1)
for i in range(1, n+1) :
DP[i] = min((DP[k] + 1 for k in range(max(0, i - 5), i) if t[k:i] in strs), default = 1e6)
return DP[-1] if DP[-1] < 1e6 else -1