LeetCode 1639. Number of Ways to Form a Target String Given a Dictionary(JAVA)

출처 : https://leetcode.com/problems/number-of-ways-to-form-a-target-string-given-a-dictionary/description/?envType=daily-question&envId=2024-12-29

 

#문제 

You are given a list of strings of the same length words and a string target.
Your task is to form target using the given words under the following rules:
target should be formed from left to right.To form the ith character (0-indexed) of target, you can choose the kth character of the jth string in words if target[i] = words[j][k].Once you use the kth character of the jth string of words, you can no longer use the xth character of any string in words where x <= k. In other words, all characters to the left of or at index k become unusuable for every string.Repeat the process until you form the string target.
Notice that you can use multiple characters from the same string in words provided the conditions above are met.
Return the number of ways to form target from words. Since the answer may be too large, return it modulo 10^9 + 7.

길이가 동일한 문자열들의 리스트 words와 문자열 target이 주어집니다.다음 규칙에 따라 words를 사용하여 target을 만드세요:
target은 왼쪽에서 오른쪽으로 순서대로 만들어야 합니다.target의 i번째 문자(0부터 시작)를 만들기 위해, words의 j번째 문자열의 k번째 문자를 선택할 수 있습니다. 단, target[i] = words[j][k]가 성립해야 합니다.words의 j번째 문자열의 k번째 문자를 사용하면, 모든 문자열에서 인덱스가 k 이하인 문자는 더 이상 사용할 수 없습니다. 즉, 모든 문자열에서 해당 문자 왼쪽의 문자들은 사용할 수 없게 됩니다.위 과정을 반복하여 target을 완성하세요.
주의: 동일한 문자열에서 여러 문자를 사용할 수 있지만, 위 조건을 만족해야 합니다.target을 만들 수 있는 방법의 수를 반환하세요. 결과는 너무 클 수 있으므로 10^9 + 7로 나눈 나머지를 반환하세요.

 

접근 : DFS +DP(Memoization)

 

words의 각 단어의 문자의 빈도수를 freq테이블에 저장, freq테이블을 탐색하며 target을 완성할수있는 경우의 수를 계산 중복계산을 피하기위해 경우의 수를 dp테이블에 저장

 

private long res = 0;
private int MOD = 1000000007;
private long[][] dp;
public int numWays(String[] words, String target) {
    int maxLen = words[0].length();
    for(int i = 0 ;i < words.length;i++){
        maxLen = Math.max(maxLen, words[i].length());
    }
    int[][] freq = new int[maxLen][26];
    for(int i = 0 ;i < words.length;i++){
        for(int j = 0; j < words[i].length();j++){
            freq[j][(int) (words[i].charAt(j)-'a')]++;
        }
    }
    //dp[i][j] 의 뜻 : freq[i]에서 target.chartAt(j) 문자를 선탣했을때의 완성할수있는 경우의 수
    dp = new long[maxLen+1][target.length()+1];
    for(int i = 0 ;i <= maxLen;i++){
        Arrays.fill(dp[i], -1);
    }

    res = dfs(freq,target,0,0,maxLen);
    return (int) res;
}
public long dfs(int[][] freq,String target,int level,int targetIndex,int limit){
    //문자를 완성했다면 +1
    if(targetIndex == target.length()){
        return 1;
    }
    //완성하지 못했다면 0
    if(level == limit){
        return 0;
    }
    if(dp[level][targetIndex] != -1){
        return dp[level][targetIndex];
    }
    //다음 레벨에서 현재의 문자를 찾는다
    long skip = dfs(freq, target, level+1, targetIndex, limit);

    //다음 레벨에서 다음 문자를 찾는다
    long next = 0;
    //현재 레벨에서 문자를 완성할수있는 경우 = 다음레벨에서 문자를 완성할수있는 경우 * 현재 문자의 갯수
    if(freq[level][target.charAt(targetIndex) - 'a'] > 0)
        next = (freq[level][target.charAt(targetIndex) - 'a'] * dfs(freq, target, level+1, targetIndex+1, limit) % MOD);


    dp[level][targetIndex] = (next+skip)%MOD;

    return dp[level][targetIndex];

}