[JS] 단어퍼즐

dp를 활용하여 해결하였다!

https://school.programmers.co.kr/learn/courses/30/lessons/12983

프로그래머스

 

 

문제 조건을 보면 DFS나 BFS로 푸는 것은 불가능한 케이스이다. 문자열의 길이가 20,000까지고 조각의 길이는 얼마 되지 않는다는 점에서 DP를 생각하게 되었다.

 

DP[i] = i번째까지의 최소 조합 수 로 두자.

 

1. t길이만큼의 DP 생성

2. str배열을 돌며 첫 시작정보를 DP에 담아둔다.

3. DP[i] = Min( DP[i - i번째를 끝조각으로 맞출 수 있는 퍼즐의 길이] + 1 , DP[i] ) 가 된다.

 

3번이 잘 이해가 가지않는다면 예시를 보자.

 

["ba", "na", "n", "a"], "banana" 
[ Infinity, 1, Infinity, Infinity, Infinity, Infinity ] : DP의 초기 상태로 ba로 시작한 경우다.

[ Infinity, 1, Infinity, Infinity, Infinity, Infinity ] : i=0 | 끝자락으로 올 수 있는 조각이 없다.
[ Infinity, 1, Infinity, Infinity, Infinity, Infinity ] : i=1 | ba과 a가 끝자락으로 올 수 있으며 Infinity+1 은 갱신되지 않는다.
[ Infinity, 1, 2, Infinity, Infinity, Infinity ] : i=2 | n이 끝자락으로 올 수 있으며 dp[1]+1인 2로 갱신된다.
[ Infinity, 1, 2, 2, Infinity, Infinity ] i=3 | na와 a가 올 수 있으며 dp[1]+1 , dp[2]+1 중 더 작은 값인 2로 갱신된다.
[ Infinity, 1, 2, 2, 3, Infinity ] i=4 | n이 올 수 있으며 dp[3]+1인 3으로 갱신된다.
[ Infinity, 1, 2, 2, 3, 3 ] i=5 | a,na가 올수 있으며 dp[3]+1,dp[2]+1중 더 작은값인 3으로 갱신된다.

 

 

 

function solution(strs, t) {
    
    
    const dp = Array(t.length).fill(Infinity)
    
    const isCanPut = (str,idx) => {
        if(idx+1<str.length) return false
        
        for(let i = 0 ; i < str.length; i++){
            if(str[str.length-i-1]!==t[idx-i]) return false
        }
        return true
    }
    
    outer : for(const str of strs){
        for(let i = 0 ; i < str.length ;i++){
            if(str[i]!==t[i]) continue outer
        }
        dp[str.length-1] = 1
    }
    
    for(let i = 0 ; i < t.length; i++){
        const tmp = strs.filter(v => isCanPut(v,i))
        for(const str of tmp) {
            if(!dp[i-str.length]) continue
            dp[i] = Math.min(dp[i-str.length]+1 , dp[i])
        }
    }
    
    return dp[dp.length-1]===Infinity ? -1 : dp[dp.length-1]
}