1639 - Number of Ways to Form a Target String Given a Dictionary (Hard)

Problem Link

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

Problem Statement

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 1e9 + 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")

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.

Approach 1: Dynamic Programming

C++

Written by @wkw

class Solution {
public:
    int numWays(vector<string>& words, string target) {
        int M = 1e9 + 7, n = words[0].size(), m = target.size();
        vector<vector<long long>> dp(n, vector<long long>(m, -1));
        vector<vector<long long>> cnt(n, vector<long long>(26));
        // count character frequency for each j-th column
        for (int i = 0; i < words.size(); i++) {
            for (int j = 0; j < n; j++) {
                cnt[j][words[i][j] - 'a']++;
            }
        }
        function<int(int,int)> dfs = [&](int i, int j) {
            // reach end of target
            if (j == m) return 1;
            // reach end of words
            if (i == n) return 0;
            if (dp[i][j] != -1) return (int) dp[i][j];
            // skip i-th character
            int res = dfs(i + 1, j), c = target[j] - 'a';
            if (cnt[i][c]) res = (res + cnt[i][c] * dfs(i + 1, j + 1)) % M;
            // memoize the result
            return (int) (dp[i][j] = res);
        };
        return dfs(0, 0);
    }
};

Python

Written by @wkw

class Solution:
    # take or not take dp
    def numWays(self, words: List[str], target: str) -> int:
        M = 10 ** 9 + 7
        n, m = len(words[0]), len(target)
        cnt = [[0] * 26 for _ in range(n)]
        # count character frequency for each j-th column
        for i in range(len(words)):
            for j in range(n):
                cnt[j][ord(words[i][j]) - ord('a')] += 1
        @lru_cache(None)
        def dfs(i, j):
            # reach target
            if j == m:
                return 1
            # reach the end of the word
            if i == n:
                return 0
            # not take
            res = dfs(i + 1, j)
            # take
            c = ord(target[j]) - ord('a')
            if cnt[i][c] > 0:
                res += cnt[i][c] * dfs(i + 1, j + 1)
            return res % M
        return dfs(0, 0)