Number of Ways to Form a Target String Given a Dictionary

• Define a recursive function solve(i, k) that returns the number of ways to form target.substring(i) using characters from words at columns j >= k.
• Base Case 1: If i == target.length(), we have successfully formed the target. Return 1.
• Base Case 2: If k == words[0].length(), we have run out of columns but not finished the target. Return 0.
• Recursive Step: The total ways are the sum of two choices:
  1. Skip column k: Don't use any character from column k. The number of ways is solve(i, k + 1).
  2. Use column k: Count the number of words words[j] where words[j][k] == target.charAt(i). Let this be count_matches. The number of ways is count_matches * solve(i + 1, k + 1).
• The final answer is solve(0, 0).

This approach tackles the problem by defining a recursive function, say solve(i, k), which calculates the number of ways to form the suffix of the target string starting at index i (target[i:]) using characters from the words dictionary at or after column k.

The base cases for the recursion are:

1. If i reaches the end of the target string (i == target.length), it means we have successfully formed the target. We return 1, signifying one valid way.
2. If k reaches the end of the columns in words (k == words[0].length) but i has not reached the end of target, it's impossible to continue. We return 0.

In the recursive step for solve(i, k), we consider two choices for forming target[i]:

1. Skip column k: We don't use any character from column k. We move to the next column to find a match for target[i]. This contributes solve(i, k + 1) ways.
2. Use column k: We find all characters in column k of words that match target[i]. Let this count be count_matches. For each match, we've formed target[i], so we need to form the rest of the target (target[i+1:]) using columns strictly greater than k. This contributes count_matches * solve(i + 1, k + 1) ways.

The total number of ways for solve(i, k) is the sum of the ways from these two choices, taken modulo 10^9 + 7. The final answer is the result of the initial call solve(0, 0).

1class Solution {2    private String[] words;3    private String target;4    private int wordLen;5    private int targetLen;6    private int MOD = 1_000_000_007;7 8    public int numWays(String[] words, String target) {9        this.words = words;10        this.target = target;11        this.wordLen = words[0].length();12        this.targetLen = target.length();13        return (int) solve(0, 0);14    }15 16    private long solve(int i, int k) {17        // Base case: successfully formed the target18        if (i == targetLen) {19            return 1;20        }21        // Base case: ran out of columns in words22        if (k == wordLen) {23            return 0;24        }25 26        // Option 1: Skip column k27        long ways = solve(i, k + 1);28 29        // Option 2: Use column k to match target[i]30        long countMatches = 0;31        for (String word : words) {32            if (word.charAt(k) == target.charAt(i)) {33                countMatches++;34            }35        }36 37        if (countMatches > 0) {38            ways = (ways + countMatches * solve(i + 1, k + 1)) % MOD;39        }40 41        return ways;42    }43}

• Pre-compute a frequency table counts[n][26] where counts[k][c] is the number of occurrences of character c in column k of all words.
• Use a memoization table memo[m][n] to store the results of subproblems, initialized to a sentinel value like -1.
• Define a recursive function solve(i, k) as in the brute-force approach.
• Inside solve(i, k), first check if memo[i][k] has a stored result. If so, return it.
• Otherwise, compute the result using the same recurrence: res = solve(i, k + 1) + counts[k][target[i]] * solve(i + 1, k + 1).
• Store the computed result in memo[i][k] before returning.

The core recursive structure remains the same as the brute-force approach, where solve(i, k) calculates the number of ways to form target[i:] using columns from k onwards. However, we introduce a 2D array, memo[m][n], to store the results of solve(i, k) once they are computed.

Before any computation inside solve(i, k), we first check if memo[i][k] already contains a valid result (i.e., not the initial sentinel value). If it does, we immediately return the stored value, avoiding a costly recursive call.

If the result is not in the memoization table, we compute it using the recurrence relation. To make this faster, we first pre-process the words list to create a frequency map, counts[n][26], where counts[k][char - 'a'] stores how many times char appears in column k across all words. This avoids iterating through all words at every step. The recurrence then becomes: ways = solve(i, k + 1) + (counts[k][target.charAt(i) - 'a'] * solve(i + 1, k + 1))

Once the result is computed, we store it in memo[i][k] before returning. This ensures that any future call to solve(i, k) will be an O(1) lookup.

1class Solution {2    private long[][] memo;3    private long[][] counts;4    private String target;5    private int wordLen;6    private int targetLen;7    private int MOD = 1_000_000_007;8 9    public int numWays(String[] words, String target) {10        this.target = target;11        this.wordLen = words[0].length();12        this.targetLen = target.length();13        this.memo = new long[targetLen][wordLen];14        for (long[] row : memo) {15            Arrays.fill(row, -1);16        }17 18        this.counts = new long[wordLen][26];19        for (String word : words) {20            for (int k = 0; k < wordLen; k++) {21                counts[k][word.charAt(k) - 'a']++;22            }23        }24 25        return (int) solve(0, 0);26    }27 28    private long solve(int i, int k) {29        if (i == targetLen) {30            return 1;31        }32        if (k == wordLen) {33            return 0;34        }35        if (memo[i][k] != -1) {36            return memo[i][k];37        }38 39        // Option 1: Skip column k40        long ways = solve(i, k + 1);41 42        // Option 2: Use column k43        long numMatches = counts[k][target.charAt(i) - 'a'];44        if (numMatches > 0) {45            ways = (ways + numMatches * solve(i + 1, k + 1)) % MOD;46        }47 48        return memo[i][k] = ways;49    }50}

• Define a 2D DP table dp[m+1][n+1], where dp[i][k] stores the number of ways to form target.substring(i) using columns from k onwards.
• Pre-compute the frequency table counts as in the memoization approach.
• Initialize Base Cases:
  • dp[m][k] = 1 for all k from 0 to n (one way to form an empty target suffix).
  • dp[i][n] = 0 for all i < m (no way to form a non-empty target with no columns).
• Fill the Table: Iterate i from m-1 down to 0 and k from n-1 down to 0.
• For each (i, k), calculate dp[i][k] using the recurrence: dp[i][k] = (dp[i][k+1] + counts[k][target[i]] * dp[i+1][k+1]) % MOD.
• The final answer is dp[0][0].

This approach converts the top-down recursive solution into an iterative one. We use a 2D array dp[m+1][n+1], where dp[i][k] stores the same value as our recursive function: the number of ways to form the suffix target[i:] using characters from columns k onwards.

The table is filled starting from the base cases. The base cases are:

• dp[m][k] = 1 for all k from 0 to n. This signifies that an empty target suffix (target[m:]) can be formed in exactly one way (by picking no more characters), regardless of the available columns.
• dp[i][n] = 0 for i < m. This signifies that if we have run out of columns (k=n) but still need to form characters, there are zero ways to succeed.

We then fill the rest of the table by iterating backwards from these base cases. The outer loop runs for i from m-1 down to 0, and the inner loop for k from n-1 down to 0. This order ensures that when we calculate dp[i][k], the values it depends on (dp[i][k+1] and dp[i+1][k+1]) have already been computed. The recurrence relation remains the same: dp[i][k] = (dp[i][k+1] + counts[k][target.charAt(i) - 'a'] * dp[i+1][k+1]) % MOD

The final answer is stored in dp[0][0], which represents the number of ways to form the entire target (target[0:]) using all available columns (k=0 onwards).

1class Solution {2    public int numWays(String[] words, String target) {3        int n = words[0].length();4        int m = target.length();5        int MOD = 1_000_000_007;6 7        long[][] counts = new long[n][26];8        for (String word : words) {9            for (int k = 0; k < n; k++) {10                counts[k][word.charAt(k) - 'a']++;11            }12        }13 14        long[][] dp = new long[m + 1][n + 1];15 16        // Base case: One way to form an empty target17        for (int k = 0; k <= n; k++) {18            dp[m][k] = 1;19        }20 21        for (int i = m - 1; i >= 0; i--) {22            for (int k = n - 1; k >= 0; k--) {23                // Option 1: Skip column k24                dp[i][k] = dp[i][k + 1];25 26                // Option 2: Use column k27                long numMatches = counts[k][target.charAt(i) - 'a'];28                if (numMatches > 0) {29                    dp[i][k] = (dp[i][k] + numMatches * dp[i + 1][k + 1]) % MOD;30                }31            }32        }33 34        return (int) dp[0][0];35    }36}

• Observe that computing dp[i][k] only requires values from row i (dp[i][k+1]) and row i+1 (dp[i+1][k+1]).
• This allows us to reduce space by only keeping track of the current row (i) and the previous row (i+1).
• We can use a single 1D array dp of size n+1.
• Initialize dp with all 1s, representing the base case for i=m.
• Iterate i from m-1 down to 0.
• For each i, iterate k from n-1 down to 0 to update the dp array in place for row i.
• To compute the new dp[k], we need the old dp[k+1] (from row i+1). We save this value in a temporary 'diagonal' variable before dp[k+1] is overwritten.
• The update rule is: new_dp[k] = new_dp[k+1] + count * old_dp[k+1].
• After the loops complete, dp[0] holds the final answer.

The space optimization builds on the bottom-up DP approach. The recurrence dp[i][k] = dp[i][k+1] + counts[k][target[i]] * dp[i+1][k+1] shows that to compute any cell dp[i][k], we only need values from its own row (dp[i][...]) and the next row (dp[i+1][...]). This means we don't need to store the entire m x n table.

We can use a single 1D array, dp of size n+1, to represent one row of the DP table. We iterate i from m-1 down to 0. In each iteration, the dp array starts by holding the values for row i+1, and we update it in-place to hold the values for row i.

To do this with a single array, we must iterate k from n-1 down to 0. When we compute the new value for dp[k], the formula needs dp[i][k+1] and dp[i+1][k+1]. Since we iterate k downwards, dp[k+1] in our array has already been updated to its value for row i, which is exactly dp[i][k+1]. However, we also need dp[i+1][k+1], which was the value at dp[k+1] before it was updated. We can manage this by saving the required value from the previous row in a temporary variable (let's call it diagonal) before it gets overwritten.

1class Solution {2    public int numWays(String[] words, String target) {3        int n = words[0].length();4        int m = target.length();5        int MOD = 1_000_000_007;6 7        long[][] counts = new long[n][26];8        for (String word : words) {9            for (int k = 0; k < n; k++) {10                counts[k][word.charAt(k) - 'a']++;11            }12        }13 14        long[] dp = new long[n + 1];15        // Base case for i = m: dp[k] = 1 for all k16        Arrays.fill(dp, 1);17 18        for (int i = m - 1; i >= 0; i--) {19            // This variable will hold the value of dp[i+1][k+1] as we iterate k downwards.20            // It starts as dp[i+1][n], which is 1.21            long diagonal = 1;22            for (int k = n - 1; k >= 0; k--) {23                // Save dp[i+1][k] before it's overwritten.24                long temp = dp[k];25                26                // dp[k+1] now holds dp[i][k+1].27                // 'diagonal' holds dp[i+1][k+1].28                long ways = dp[k + 1]; // Option 1: Skip column k29                long numMatches = counts[k][target.charAt(i) - 'a'];30                if (numMatches > 0) {31                    ways = (ways + numMatches * diagonal) % MOD; // Option 2: Use column k32                }33                dp[k] = ways;34 35                // Update diagonal for the next iteration of k (k-1).36                // The new diagonal will be dp[i+1][k], which we saved in temp.37                diagonal = temp;38            }39        }40 41        return (int) dp[0];42    }43}