# Number of Ways to Form a Target String Given a Dictionary
**Difficulty:** HARD
[External](https://leetcode.com/problems/number-of-ways-to-form-a-target-string-given-a-dictionary)
Canonical: https://scaleengineer.com/dsa/problems/number-of-ways-to-form-a-target-string-given-a-dictionary
**Patterns:** [Dynamic Programming](https://scaleengineer.com/dsa/patterns/dynamic-programming)
**Data structures:** Array, String
**Companies:** [Snowflake](https://scaleengineer.com/companies/snowflake), [Dunzo](https://scaleengineer.com/companies/dunzo)
---
## Problem
You are given a list of strings of the **same length** `words` and a string `target`.

Your task is to form `target` using the given `words` under the following rules:

* `target` should be formed from left to right.
* To form the `ith` character (**0-indexed**) of `target`, you can choose the `kth` character of the `jth` string in `words` if `target[i] = words[j][k]`.
* Once you use the `kth` character of the `jth` string of `words`, you **can no longer** use the `xth` character of any string in `words` where `x <= k`. In other words, all characters to the left of or at index `k` become unusuable for every string.
* Repeat the process until you form the string `target`.

**Notice** that you can use **multiple characters** from the **same string** in `words` provided the conditions above are met.

Return _the number of ways to form `target` from `words`_. Since the answer may be too large, return it **modulo** `109 + 7`.

**Example 1:**

**Input:** words = ["acca","bbbb","caca"], target = "aba"
**Output:** 6
**Explanation:** There are 6 ways to form target.
"aba" -> index 0 ("acca"), index 1 ("bbbb"), index 3 ("caca")
"aba" -> index 0 ("acca"), index 2 ("bbbb"), index 3 ("caca")
"aba" -> index 0 ("acca"), index 1 ("bbbb"), index 3 ("acca")
"aba" -> index 0 ("acca"), index 2 ("bbbb"), index 3 ("acca")
"aba" -> index 1 ("caca"), index 2 ("bbbb"), index 3 ("acca")
"aba" -> index 1 ("caca"), index 2 ("bbbb"), index 3 ("caca")

**Example 2:**

**Input:** words = ["abba","baab"], target = "bab"
**Output:** 4
**Explanation:** There are 4 ways to form target.
"bab" -> index 0 ("baab"), index 1 ("baab"), index 2 ("abba")
"bab" -> index 0 ("baab"), index 1 ("baab"), index 3 ("baab")
"bab" -> index 0 ("baab"), index 2 ("baab"), index 3 ("baab")
"bab" -> index 1 ("abba"), index 2 ("baab"), index 3 ("baab")

**Constraints:**

* `1 <= words.length <= 1000`
* `1 <= words[i].length <= 1000`
* All strings in `words` have the same length.
* `1 <= target.length <= 1000`
* `words[i]` and `target` contain only lowercase English letters.

# Approaches
## Brute-Force Recursion
A straightforward recursive approach that explores all possible ways to form the target string. It directly translates the problem's rules into a recursive function without any optimization for overlapping subproblems.
**Time:** O(W * 2^(m+n)), where `W` is `words.length`, `m` is `target.length`, and `n` is `words[0].length`. This is because the recursion tree can have a depth of `m+n` with a branching factor of 2, and at each node, we iterate through `W` words. · **Space:** O(m + n), for the recursion stack depth, where `m` is the length of `target` and `n` is the length of the words.
**Pros:** Simple to conceptualize and implement as it directly follows the problem statement.
**Cons:** Extremely inefficient due to massive re-computation of the same subproblems.; Will result in a 'Time Limit Exceeded' (TLE) error for all but the smallest inputs.
### Explanation
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)`.

```java
class Solution {
    private String[] words;
    private String target;
    private int wordLen;
    private int targetLen;
    private int MOD = 1_000_000_007;

    public int numWays(String[] words, String target) {
        this.words = words;
        this.target = target;
        this.wordLen = words[0].length();
        this.targetLen = target.length();
        return (int) solve(0, 0);
    }

    private long solve(int i, int k) {
        // Base case: successfully formed the target
        if (i == targetLen) {
            return 1;
        }
        // Base case: ran out of columns in words
        if (k == wordLen) {
            return 0;
        }

        // Option 1: Skip column k
        long ways = solve(i, k + 1);

        // Option 2: Use column k to match target[i]
        long countMatches = 0;
        for (String word : words) {
            if (word.charAt(k) == target.charAt(i)) {
                countMatches++;
            }
        }

        if (countMatches > 0) {
            ways = (ways + countMatches * solve(i + 1, k + 1)) % MOD;
        }

        return ways;
    }
}
```
### Algorithm
- 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)`.

## Top-Down Dynamic Programming with Memoization
This approach improves upon the brute-force recursion by storing the results of subproblems in a memoization table (a 2D array). This avoids redundant calculations for the same state `(i, k)`, drastically reducing the time complexity from exponential to polynomial.
**Time:** O(W * n + m * n), where `W` is `words.length`, `m` is `target.length`, and `n` is `words[0].length`. `O(W * n)` is for pre-computing frequencies, and `O(m * n)` for the DP part, as there are `m * n` states, each taking `O(1)` to compute. · **Space:** O(m * n) for the memoization table. An additional `O(n)` for the frequency counts and `O(m+n)` for the recursion stack. The dominant factor is `O(m * n)`.
**Pros:** Significantly more efficient than brute-force, with polynomial time complexity.; Guaranteed to compute each subproblem only once.; Often more intuitive to write than the bottom-up (iterative) DP approach.
**Cons:** May cause a stack overflow for very deep recursion, though the given constraints should be fine.; Has the overhead of recursive function calls compared to an iterative solution.
### Explanation
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.

```java
class Solution {
    private long[][] memo;
    private long[][] counts;
    private String target;
    private int wordLen;
    private int targetLen;
    private int MOD = 1_000_000_007;

    public int numWays(String[] words, String target) {
        this.target = target;
        this.wordLen = words[0].length();
        this.targetLen = target.length();
        this.memo = new long[targetLen][wordLen];
        for (long[] row : memo) {
            Arrays.fill(row, -1);
        }

        this.counts = new long[wordLen][26];
        for (String word : words) {
            for (int k = 0; k < wordLen; k++) {
                counts[k][word.charAt(k) - 'a']++;
            }
        }

        return (int) solve(0, 0);
    }

    private long solve(int i, int k) {
        if (i == targetLen) {
            return 1;
        }
        if (k == wordLen) {
            return 0;
        }
        if (memo[i][k] != -1) {
            return memo[i][k];
        }

        // Option 1: Skip column k
        long ways = solve(i, k + 1);

        // Option 2: Use column k
        long numMatches = counts[k][target.charAt(i) - 'a'];
        if (numMatches > 0) {
            ways = (ways + numMatches * solve(i + 1, k + 1)) % MOD;
        }

        return memo[i][k] = ways;
    }
}
```
### Algorithm
- 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.

## Bottom-Up Dynamic Programming
This is an iterative version of the memoized recursion. It builds the solution from the base cases up to the final answer, `dp[0][0]`, using a 2D DP table. This avoids recursion and its associated overhead, which can lead to slightly better performance.
**Time:** O(W * n + m * n). `O(W * n)` for pre-computation and `O(m * n)` for filling the DP table. · **Space:** O(m * n) for the DP table, plus `O(n)` for the frequency counts.
**Pros:** Avoids recursion overhead and the risk of stack overflow.; Can be slightly faster in practice than the top-down approach due to better cache locality and no function call overhead.
**Cons:** The order of loops and state transitions might be less intuitive to derive compared to the recursive solution.; Uses a large amount of memory (`O(m*n)`) which can be optimized.
### Explanation
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).

```java
class Solution {
    public int numWays(String[] words, String target) {
        int n = words[0].length();
        int m = target.length();
        int MOD = 1_000_000_007;

        long[][] counts = new long[n][26];
        for (String word : words) {
            for (int k = 0; k < n; k++) {
                counts[k][word.charAt(k) - 'a']++;
            }
        }

        long[][] dp = new long[m + 1][n + 1];

        // Base case: One way to form an empty target
        for (int k = 0; k <= n; k++) {
            dp[m][k] = 1;
        }

        for (int i = m - 1; i >= 0; i--) {
            for (int k = n - 1; k >= 0; k--) {
                // Option 1: Skip column k
                dp[i][k] = dp[i][k + 1];

                // Option 2: Use column k
                long numMatches = counts[k][target.charAt(i) - 'a'];
                if (numMatches > 0) {
                    dp[i][k] = (dp[i][k] + numMatches * dp[i + 1][k + 1]) % MOD;
                }
            }
        }

        return (int) dp[0][0];
    }
}
```
### Algorithm
- 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]`.

## Space-Optimized Bottom-Up Dynamic Programming
This approach optimizes the space complexity of the bottom-up DP. By observing the state transition dependencies, we see that computing the values for the current row `i` only requires information from the immediately previous row `i+1`. This allows us to reduce the space from a 2D table `O(m*n)` to a 1D array `O(n)`, making it the most memory-efficient solution.
**Time:** O(W * n + m * n). The asymptotic time complexity remains the same as the unoptimized DP solutions. · **Space:** O(n), for the DP array and the frequency counts. This is a significant improvement over `O(m * n)` when `m` is large.
**Pros:** Most efficient in terms of space complexity.; Retains the optimal time efficiency of the other DP approaches.
**Cons:** The logic for in-place updates using a single array can be tricky to get right and is less straightforward to read and debug.
### Explanation
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.

```java
class Solution {
    public int numWays(String[] words, String target) {
        int n = words[0].length();
        int m = target.length();
        int MOD = 1_000_000_007;

        long[][] counts = new long[n][26];
        for (String word : words) {
            for (int k = 0; k < n; k++) {
                counts[k][word.charAt(k) - 'a']++;
            }
        }

        long[] dp = new long[n + 1];
        // Base case for i = m: dp[k] = 1 for all k
        Arrays.fill(dp, 1);

        for (int i = m - 1; i >= 0; i--) {
            // This variable will hold the value of dp[i+1][k+1] as we iterate k downwards.
            // It starts as dp[i+1][n], which is 1.
            long diagonal = 1;
            for (int k = n - 1; k >= 0; k--) {
                // Save dp[i+1][k] before it's overwritten.
                long temp = dp[k];
                
                // dp[k+1] now holds dp[i][k+1].
                // 'diagonal' holds dp[i+1][k+1].
                long ways = dp[k + 1]; // Option 1: Skip column k
                long numMatches = counts[k][target.charAt(i) - 'a'];
                if (numMatches > 0) {
                    ways = (ways + numMatches * diagonal) % MOD; // Option 2: Use column k
                }
                dp[k] = ways;

                // Update diagonal for the next iteration of k (k-1).
                // The new diagonal will be dp[i+1][k], which we saved in temp.
                diagonal = temp;
            }
        }

        return (int) dp[0];
    }
}
```
### Algorithm
- 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.

# Solutions
### Java

```java
class Solution { private int m ; private int n ; private String target ; private Integer [][] f ; private int [][] cnt ; private final int mod = ( int ) 1 e9 + 7 ; public int numWays ( String [] words , String target ) { m = target . length (); n = words [ 0 ]. length (); f = new Integer [ m ][ n ]; this . target = target ; cnt = new int [ n ][ 26 ]; for ( var w : words ) { for ( int j = 0 ; j < n ; ++ j ) { cnt [ j ][ w . charAt ( j ) - 'a' ]++; } } return dfs ( 0 , 0 ); } private int dfs ( int i , int j ) { if ( i >= m ) { return 1 ; } if ( j >= n ) { return 0 ; } if ( f [ i ][ j ] != null ) { return f [ i ][ j ]; } long ans = dfs ( i , j + 1 ); ans += 1L * dfs ( i + 1 , j + 1 ) * cnt [ j ][ target . charAt ( i ) - 'a' ]; ans %= mod ; return f [ i ][ j ] = ( int ) ans ; } }
```

### CPP

```cpp
class Solution { public: int numWays ( vector < string >& words , string target ) { const int mod = 1e9 + 7 ; int m = target . size (), n = words [ 0 ]. size (); vector < vector < int >> cnt ( n , vector < int > ( 26 )); for ( auto & w : words ) { for ( int j = 0 ; j < n ; ++ j ) { ++ cnt [ j ][ w [ j ] - 'a' ]; } } int f [ m ][ n ]; memset ( f , - 1 , sizeof ( f )); function < int ( int , int ) > dfs = [ & ]( int i , int j ) -> int { if ( i >= m ) { return 1 ; } if ( j >= n ) { return 0 ; } if ( f [ i ][ j ] != - 1 ) { return f [ i ][ j ]; } int ans = dfs ( i , j + 1 ); ans = ( ans + 1LL * dfs ( i + 1 , j + 1 ) * cnt [ j ][ target [ i ] - 'a' ]) % mod ; return f [ i ][ j ] = ans ; }; return dfs ( 0 , 0 ); } };
```

### Python

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