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).
This solution constructs a DP table where `dp[i][j]` represents the number of ways to form the first `i` characters of the target using the first `j` characters (positions) of the words. The `count` table stores how many times each character appears at each position in `words`. We update the DP table row by row for each position in the target by combining counts from the `count` table and previous DP states.
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).
1import java.util.Arrays;
2
3class Solution {
4 private static final int MOD = 1000000007;
5 private int[][] dp;
6 private int[][] count;
7
8 private int dfs(String target, int i, int j, int m) {
9 if (i == target.length()) return 1;
10 if (j == m) return 0;
11 if (dp[i][j] != -1) return dp[i][j];
12
13 int res = dfs(target, i, j + 1, m);
14 if (count[j][target.charAt(i) - 'a'] > 0) {
15 res = (int)((res + (long)count[j][target.charAt(i) - 'a'] * dfs(target, i + 1, j + 1, m)) % MOD);
16 }
17
18 return dp[i][j] = res;
19 }
20
21 public int numWays(String[] words, String target) {
22 int m = words[0].length();
23 dp = new int[target.length()][m];
24 for (int[] row : dp) Arrays.fill(row, -1);
25 count = new int[m][26];
26
27 for (String word : words)
28 for (int i = 0; i < m; ++i)
29 count[i][word.charAt(i) - 'a']++;
30
31 return dfs(target, 0, 0, m);
32 }
33}
34The Java version mirrors the memoization process using a recursive approach with stored `dp` results. The `count` array tracks character occurences, aiding efficient calculation and avoiding redundant evaluations for the solution.