[LeetCode] 1639. Number of Ways to Form a Target String Given a Dictionary

https://leetcode.com/problems/number-of-ways-to-form-a-target-string-given-a-dictionary/description/

leetcode - Number of Ways to Form a Target String Given a Dictionary

문제 유형: 다이나믹 프로그래밍, 문자열 처리

문제 난이도: Hard

 

문제

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이 주어진다.

다음의 룰로 target을 구성해야 한다:

• target은 left부터 right순으로 만들어져야 한다.
• target[i]를 구성하기 위해, target[i] = words[j][k]에 해당하는 문자를 찾을 수 있다.
• j번째 단어의 k번째글자를 고르면, k인덱스 이전의 문자는 사용될 수 없다.

값이 클 수 있으니,  mod 10^9+7로 구하시오.

 

풀이

freq[col] = 해당 column이후의 알파벳 개수(26길이 정수배열)로 구성한다.

즉, 1번째 컬럼 이후의 알바펫 'b'의 개수는

freq[col]['b' - 'a' = 2]가 된다.

이렇게 freq배열을 미리 계산해서 개수를 저장해놓는다.

 

그 뒤, 이제 구성해보면 된다.

dp[i] = target[i-1]까지의 부분문자열을 구성하는 경우의 수로 한다.

dp[0]은 빈 문자열의 경우로, 1가지가 있다.

 

각 컬럼에 대해서 경우의 수를 누적할 것이다.

column-order로 문제를 풀이해야 순차적으로 풀 수 있다.

각 컬럼에 대해서, 역순으로 부분문자여에 대해 순회하면서, (for i=l; i>=1; --i)...

개수 freq[col][target[i-1] - 'a']가 양수라면, dp[i]에 이전 dp인 dp[i-1]에 개수를 곱해서 더하고, MOD로 나눈다.

 

최종적인 target[l]을 리턴하면 된다.

 

코드

C++

class Solution {
public:
    int numWays(vector<string>& words, string target) {
        int n = words.size();
        int m = words[0].size();
        int l = target.size();
        const int MOD = 1e9 + 7;

        vector<vector<int>> freq(m, vector<int>(26, 0)); // freq[col][alphabet]
        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < m; ++j) {
                freq[j][words[i][j] - 'a']++;
            }
        }

        vector<int> dp(l + 1, 0); // dp[substring len] = number of ways to make target[0:substring len-1]
        dp[0] = 1;

        for (int col = 0; col < m; ++col) {
            for (int i = l; i >= 1; --i) {
                if (freq[col][target[i-1] - 'a'] > 0) {
                    dp[i] = (dp[i] + (long long)dp[i-1] * freq[col][target[i-1] - 'a']) % MOD;
                }
            }
        }
        return dp[l];
    }
};