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).
1#include <vector>
2#include <string>
3using namespace std;
4
5class Solution {
6public:
7 int numWays(vector<string>& words, string target) {
8 const int MOD = 1e9 + 7;
9 int m = words[0].size(), t = target.size();
10 vector<vector<int>> dp(t+1, vector<int>(m+1));
11 vector<vector<int>> count(m, vector<int>(26));
12
13 for (const string& word : words)
14 for (int i = 0; i < m; ++i)
15 ++count[i][word[i] - 'a'];
16
17 dp[0][0] = 1;
18 for (int j = 0; j < m; ++j)
19 dp[0][j+1] = 1;
20
21 for (int i = 1; i <= t; ++i) {
22 for (int j = 1; j <= m; ++j) {
23 dp[i][j] = dp[i][j-1];
24 if (count[j-1][target[i-1] - 'a'] > 0)
25 dp[i][j] = (dp[i][j] + (long long)dp[i-1][j-1] * count[j-1][target[i-1] - 'a']) % MOD;
26 }
27 }
28
29 return dp[t][m];
30 }
31};
32This C++ solution follows the same dynamic programming strategy as the C solution, building a DP table to keep track of how many ways the target string can be formed up to each character, considering all positions up to the current one in the given words. The frequency count of each character in words helps to efficiently compute the ways for the DP state transitions.
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).
This solution employs a recursive depth-first search (`dfs`) with memoization. The function `dfs(i, j)` returns the number of ways to form the target string starting from index `i` of the target and index `j` of a word in `words`. The memoized `dp` array stores results of overlapping subproblems to avoid recalculations.