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

Problem Description

Given a list of strings words of the same length and a string target, the task is to find the number of ways to form target using characters from words. The rules are:

1. target is formed from left to right.
2. To form the i-th character of target, you can choose the k-th character of the j-th string in words if target[i] == words[j][k].
3. Once you use the k-th character of the j-th string, you cannot use any character at index less than or equal to k in any string.
4. Multiple characters from the same string can be used.

The answer should be returned modulo 109 + 7.

Solution Approach

The problem can be efficiently solved using dynamic programming (DP) or memoization (top-down DP). Both approaches rely on preprocessing the input to count character frequencies at each position in words.

Preprocessing:

We create a 2D array cnt where cnt[j][c] represents the count of character c at position j across all strings in words.

Dynamic Programming (Bottom-Up):

We use a DP table f[i][j] where f[i][j] represents the number of ways to form the first i characters of target using characters up to position j in words.

• Base case: f[0][j] = 1 for all j (empty target can be formed in one way).
• Recurrence relation: f[i][j] = f[i][j-1] + f[i-1][j-1] * cnt[j-1][target[i-1] - 'a']. This means either we don't use the j-th position of the words ( f[i][j-1] ), or we do use it ( f[i-1][j-1] * cnt[j-1][target[i-1] - 'a'] ).

The final answer is f[target.length][words[0].length].

Memoization (Top-Down):

A recursive function dfs(i, j) counts the number of ways to form target[i:] using characters from position j onwards in words.

• Base case: If i reaches the end of target, return 1 (success). If j reaches the end of words, return 0 (failure).
• Recursive step: dfs(i, j) calls dfs(i, j+1) (skip the j-th position) and dfs(i+1, j+1) * cnt[j][target[i] - 'a'] (use the j-th position if possible).

Both approaches have a time complexity of O(mn) where m is the length of target and n is the length of each string in words. The space complexity is also O(mn) for the DP table or memoization.

Code Implementation (Python, Java, C++, Go)

The code implementations below demonstrate both the DP and memoization approaches. The memoization approach is presented in Python and Java to highlight the equivalence and differences in implementation style compared to the iterative DP approach.

Python (DP):

class Solution:
    def numWays(self, words: List[str], target: str) -> int:
        m, n = len(target), len(words[0])
        cnt = [[0] * 26 for _ in range(n)]
        for word in words:
            for j, c in enumerate(word):
                cnt[j][ord(c) - ord('a')] += 1
        mod = 10**9 + 7
        dp = [[0] * (n + 1) for _ in range(m + 1)]
        for j in range(n + 1):
            dp[0][j] = 1
        for i in range(1, m + 1):
            for j in range(1, n + 1):
                dp[i][j] = (dp[i][j - 1] + dp[i - 1][j - 1] * cnt[j - 1][ord(target[i - 1]) - ord('a')]) % mod
        return dp[m][n]
 

Java (DP):

class Solution {
    public int numWays(String[] words, String target) {
        int m = target.length();
        int n = words[0].length();
        int[][] cnt = new int[n][26];
        for (String word : words) {
            for (int j = 0; j < n; ++j) {
                cnt[j][word.charAt(j) - 'a']++;
            }
        }
        long[][] dp = new long[m + 1][n + 1];
        Arrays.fill(dp[0], 1);
        int mod = (int) 1e9 + 7;
        for (int i = 1; i <= m; ++i) {
            for (int j = 1; j <= n; ++j) {
                dp[i][j] = (dp[i][j - 1] + dp[i - 1][j - 1] * cnt[j - 1][target.charAt(i - 1) - 'a']) % mod;
            }
        }
        return (int) dp[m][n];
    }
}

C++ (DP):

class Solution {
public:
    int numWays(vector<string>& words, string target) {
        int m = target.length();
        int n = words[0].length();
        vector<vector<int>> cnt(n, vector<int>(26, 0));
        for (const string& word : words) {
            for (int j = 0; j < n; ++j) {
                cnt[j][word[j] - 'a']++;
            }
        }
        long long dp[m + 1][n + 1];
        memset(dp, 0, sizeof(dp));
        for (int j = 0; j <= n; ++j) dp[0][j] = 1;
        long long mod = 1e9 + 7;
        for (int i = 1; i <= m; ++i) {
            for (int j = 1; j <= n; ++j) {
                dp[i][j] = (dp[i][j - 1] + dp[i - 1][j - 1] * cnt[j - 1][target[i - 1] - 'a']) % mod;
            }
        }
        return dp[m][n];
    }
};

Go (DP):

func numWays(words []string, target string) int {
	m, n := len(target), len(words[0])
	cnt := make([][26]int, n)
	for _, w := range words {
		for j, c := range w {
			cnt[j][c-'a']++
		}
	}
	dp := make([][]int, m+1)
	for i := range dp {
		dp[i] = make([]int, n+1)
	}
	for j := 0; j <= n; j++ {
		dp[0][j] = 1
	}
	mod := int(1e9 + 7)
	for i := 1; i <= m; i++ {
		for j := 1; j <= n; j++ {
			dp[i][j] = (dp[i][j-1] + dp[i-1][j-1]*cnt[j-1][target[i-1]-'a']) % mod
		}
	}
	return dp[m][n]
}

These code examples provide a complete solution to the problem using dynamic programming. Remember to handle modulo operations correctly to prevent integer overflow. The time and space complexities remain O(m*n) for all implementations.