230315 단어 퍼즐

public static int solution(String[] strs, String t) {
    int[] dp = new int[t.length()];

    for (int i = 0; i < t.length(); i++) {
        updateDp(strs, t, dp, i);
    }
    return dp[t.length() - 1] == 0 ? -1 : dp[t.length() - 1];

}

private static void updateDp(String[] strs, String t, int[] dp, int i) {
    for (String word : strs) {
        int tempIdx = i - word.length() + 1;
        if (tempIdx >= 0 && word.equals(t.substring(tempIdx, i + 1))) {
            if (tempIdx == 0) {
                dp[i] = 1;
                continue;
            }
            if (dp[tempIdx - 1] > 0) {
                dp[i] = dp[i] == 0 ? dp[tempIdx - 1] + 1 : Math.min(dp[i], dp[tempIdx - 1] + 1);
            }
        }
    }
}