단어 퍼즐

주어진 문장을 완성하기 위해 사용해야 하는 단어조각 개수의 최솟값을 return 하도록 solution 함수를 완성해 주세요. 만약 주어진 문장을 완성하는 것이 불가능하면 -1을 return 하세요.

제한사항
strs는 사용 가능한 단어 조각들이 들어있는 배열로, 길이는 1 이상 100 이하입니다.
strs의 각 원소는 사용 가능한 단어조각들이 중복 없이 들어있습니다.
사용 가능한 단어 조각들은 문자열 형태이며, 모든 단어 조각의 길이는 1 이상 5 이하입니다.
t는 완성해야 하는 문자열이며 길이는 1 이상 20,000 이하입니다.
모든 문자열은 알파벳 소문자로만 이루어져 있습니다.

풀이

일단 문제를 보니 트라이 혹은 DP 문제같았다. 단어에 대한 그다음 단어를 찾기만하면 되므로
다만 단어조각 개수의 최솟값을 리턴하는걸 보면 DP가 더 편하게 풀수 있을거같아 DP를 선택했다.

먼저 dp의 크기는 앞에서부터 계산하므로 t+1의 길이만큼 가져야한다(0을 사용하지않음)
이제 i번의 크기의 대한 strs에서 나올수있는 크기의 코드를 모두 구하면서 넘어가면된다.

코드

class Solution {
    public int solution(String[] strs, String t) {
        //str의 길이
        int strLength = strs.length;
        // t의 길이 
        int tLength = t.length()+1;
        // dp
        int[] dp = new int[tLength+1]; //0번째는 값이 없음 
        
        for(int i=1;i<tLength;i++){
            for(int j=0;j<strLength;j++){
                int token = strs[j].length();
                //만약 현재까지의 길이보다 이번에 받은 문자열이 길면 음수 
                if(i-token<0) continue;
                //만약 현재 지금까지길이에서 문자를 받았을때 만들수있다면 예를 들어 ba를 만났는데 ba가 str에 존재한다면?
                if(strs[j].equals(t.substring(i-token,i))){
                    if(i-token==0){
                        //같은 단어가 존재할수없으므로 dp[i] =1;
                        dp[i] = 1; 
                        continue;
                    }
                    if(dp[i-token]>0){// 이전 dp값이 존재한다. -> 이전에 만든 문자열이 존재함.
                        //dp의 값이 0이 아닐경우에는 그냥 문자열에 +1 있다면 기존 dp값과 비교해서 가장 낮은 값을 넣음.
                        dp[i]=dp[i]==0?dp[i-token]+1:Math.min(dp[i],dp[i-token]+1);
                        
                    }
                }
            }
            
        }
        int answer = dp[tLength-1];
        if(answer==0) return -1;
                                   

        return answer;
    }
}