Sponsored
Sponsored
This approach utilizes dynamic programming along with a frequency table to keep track of the count of each character at each column index across the given words. We calculate ways to form the target string by building up solutions to subproblems of forming prefixes of the target string using the letter frequency information efficiently.
Time Complexity: O(n*m + m*t), where n is the number of words, m is the length of each word, and t is the length of the target string.
Space Complexity: O(m*t).
1def numWays(words, target):
2 MOD = 10**9 + 7
3 m, t = len(words[0]), len(target)
4 dp = [[0] * (m + 1) for _ in range(t + 1)]
5 count = [[0] * 26 for _ in range(m)]
6
7 for word in words:
8 for i, char in enumerate(word):
9 count[i][ord(char) - ord('a')] += 1
10
11 for j in range(m + 1):
12 dp[0][j] = 1
13
14 for i in range(1, t + 1):
15 for j in range(1, m + 1):
16 dp[i][j] = dp[i][j - 1]
17 if count[j - 1][ord(target[i - 1]) - ord('a')] > 0:
18 dp[i][j] = (dp[i][j] + dp[i - 1][j - 1] * count[j - 1][ord(target[i - 1]) - ord('a')]) % MOD
19
20 return dp[t][m]
21This Python solution mirrors the dynamic programming approach from previous languages. It establishes a DP table to compute the number of ways to form subsequences of the target using columns of characters from words, relying on a frequency table to count possible contributions from each column. The results are accumulated and returned modular.
This approach uses memoization to optimize the recursion while forming the target. We compute ways from each index of target and position of words and save computed results to avoid redundant calculations. This approach is effective in reducing the exponential time complexity without deep overlapping subproblems.
Time Complexity: O(n*m + m*t), optimized with memoization.
Space Complexity: O(m*t).
public class Solution {
private const int MOD = 1000000007;
private int[,] dp;
private int[,] count;
private int Dfs(string target, int i, int j, int m) {
if (i == target.Length) return 1;
if (j == m) return 0;
if (dp[i, j] != -1) return dp[i, j];
int res = Dfs(target, i, j + 1, m);
if (count[j, target[i] - 'a'] > 0) {
res = (int)((res + (long)count[j, target[i] - 'a'] * Dfs(target, i + 1, j + 1, m)) % MOD);
}
dp[i, j] = res;
return res;
}
public int NumWays(string[] words, string target) {
int m = words[0].Length;
dp = new int[target.Length, m + 1];
count = new int[m, 26];
Array.Fill(dp, -1);
foreach (var word in words)
for (int i = 0; i < m; ++i)
count[i, word[i] - 'a']++;
return Dfs(target, 0, 0, m);
}
}
The C# implementation uses a recursive strategy enhanced with a memoization technique. This solution avoids redundant calculations by leveraging a `dp` cache for previously computed results, reducing the time complexity drastically.