1639

1639. 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 109 + 7.

 

Example 1:

Input: words = ["acca","bbbb","caca"], target = "aba"
Output: 6
Explanation: There are 6 ways to form target.
"aba" -> index 0 ("acca"), index 1 ("bbbb"), index 3 ("caca")
"aba" -> index 0 ("acca"), index 2 ("bbbb"), index 3 ("caca")
"aba" -> index 0 ("acca"), index 1 ("bbbb"), index 3 ("acca")
"aba" -> index 0 ("acca"), index 2 ("bbbb"), index 3 ("acca")
"aba" -> index 1 ("caca"), index 2 ("bbbb"), index 3 ("acca")
"aba" -> index 1 ("caca"), index 2 ("bbbb"), index 3 ("caca")

Example 2:

Input: words = ["abba","baab"], target = "bab"
Output: 4
Explanation: There are 4 ways to form target.
"bab" -> index 0 ("baab"), index 1 ("baab"), index 2 ("abba")
"bab" -> index 0 ("baab"), index 1 ("baab"), index 3 ("baab")
"bab" -> index 0 ("baab"), index 2 ("baab"), index 3 ("baab")
"bab" -> index 1 ("abba"), index 2 ("baab"), index 3 ("baab")

Example 3:

Input: words = ["abcd"], target = "abcd"
Output: 1

Example 4:

Input: words = ["abab","baba","abba","baab"], target = "abba"
Output: 16

 

Constraints:

• 1 <= words.length <= 1000
• 1 <= words[i].length <= 1000
• All strings in words have the same length.
• 1 <= target.length <= 1000
• words[i] and target contain only lowercase English letters.

Related Topics:
Dynamic Programming

Solution 1. DP

Intuition: we can think of flattening the words array into a string where each place has multiple character options. And we use this spacial string to match target.

We first do the flattening using a cnt array, where cnt[i] stores the frequencies of characters at position i in words.

Let dp[i+1][j+1] be the number of ways to match target[0..j] using cnt[0..i].

When j == 0, we have only target[0] to match, we have two options:

1. Use cnt[i] to match. There are cnt[i][target[j] - 'a'] ways.
2. Reuse dp[i][j + 1] which covers the cases where we use cnt[j], j < i to match target[0].

So dp[i + 1][j + 1] = cnt[i][target[j] - 'a'] + dp[i][j + 1] when j == 0.

When j > 0, we have two options:

1. Use cnt[i] to match target[j]. There are cnt[i][target[j] - 'a'] ways to match the last character, and for the leading part there are dp[i][j] ways. So in total there are cnt[i][target[j] - 'a'] * dp[i][j] ways.
2. Reuse the dp[i][j + 1] which covers the cases where we use cnt[j], j < i to match target[j].

So dp[i + 1][j + 1] = cnt[i][target[j] - 'a'] * dp[i][j] + dp[i][j + 1] when j > 0.

We can merge these two cases by treating dp[i][j] = 1 if j == 0:

dp[i + 1][j + 1] = cnt[i][target[j] - 'a'] * dp[i][j] + dp[i][j + 1] where 0 <= i < L, 0 <= j < N

dp[i][0] = 1

dp[i + 1][j + 1] = 0 if i < j

The answer is dp[L][N].

// OJ: https://leetcode.com/problems/number-of-ways-to-form-a-target-string-given-a-dictionary/
// Author: github.com/lzl124631x
// Time: O(LM + LN)
// Space: O(LN)
class Solution {
public:
    int numWays(vector<string>& A, string target) {
        long mod = 1e9+7, M = A.size(), L = A[0].size(), N = target.size();
        if (L < N) return 0;
        vector<array<long, 26>> cnt(L, array<long, 26>());
        for (int i = 0; i < L; ++i) {
            for (int j = 0; j < M; ++j) cnt[i][A[j][i] - 'a']++;
        }
        vector<vector<int>> dp(L + 1, vector<int>(N + 1));
        for (int i = 0; i < L; ++i) {
            dp[i][0] = 1;
            for (int j = 0; j <= i && j < N; ++j) {
                dp[i + 1][j + 1] = ((cnt[i][target[j] - 'a'] * dp[i][j]) % mod + dp[i][j + 1]) % mod;
            }
        }
        return dp[L][N];
    }
};

Solution 2. DP with Space Optimization

Since dp[i + 1][j + 1] only depends on dp[i][j] and dp[i][j + 1], we can flatten the dp array from L * N to 1 * N.

// OJ: https://leetcode.com/problems/number-of-ways-to-form-a-target-string-given-a-dictionary/
// Author: github.com/lzl124631x
// Time: O(LM + LN)
// Space: O(L + N)
class Solution {
public:
    int numWays(vector<string>& A, string target) {
        long mod = 1e9+7, M = A.size(), L = A[0].size(), N = target.size();
        if (L < N) return 0;
        vector<array<long, 26>> cnt(L, array<long, 26>());
        for (int i = 0; i < L; ++i) {
            for (int j = 0; j < M; ++j) cnt[i][A[j][i] - 'a']++;
        }
        vector<long> dp(N + 1);
        for (int i = 0; i < L; ++i) {
            int prev = 1;
            for (int j = 0; j <= i && j < N; ++j) {
                int cur = dp[j + 1];
                dp[j + 1] = ((cnt[i][target[j] - 'a'] * prev) % mod + dp[j + 1]) % mod;
                prev = cur;
            }
        }
        return dp[N];
    }
};