> ## Documentation Index
> Fetch the complete documentation index at: https://leetcode-py.wisl.dev/llms.txt
> Use this file to discover all available pages before exploring further.

> ## Agent Instructions
> leetcode-py is a Python LeetCode practice environment generator with one CLI: lcpy. It is not a service or platform.
> Each problem is a directory under leetcode/ with README.md, solution.py, test_solution.py, helpers.py, and playground.ipynb. lcpy gen creates them from JSON templates bundled with the package.
> Examples are backed by tests; copy them verbatim.

# Number of Ways to Form a Target String Given

> Tested Python solution for LeetCode 1639 with 21 pytest cases. Generate a practice environment with lcpy.

LeetCode 1639, [Hard](/catalog/hard). Topics: [Array](/catalog/topics/array), [String](/catalog/topics/string), [Dynamic Programming](/catalog/topics/dynamic-programming). [View on LeetCode](https://leetcode.com/problems/number-of-ways-to-form-a-target-string-given-a-dictionary/description/).

Generate this problem as a practice environment: tested reference solution, 21 [parametrized pytest cases](/practice/testing), and a playground notebook:

```bash theme={"theme":{"light":"github-light","dark":"github-dark"}}
lcpy gen -n 1639   # by problem number
lcpy gen -s number_of_ways_to_form_a_target_string_given_a_dictionary   # by problem name
```

## 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 `i`th character (0-indexed) of `target`, you can choose the `k`th character of the `j`th string in `words` if `target[i] = words[j][k]`.
* Once you use the `k`th character of the `j`th string of `words`, you can no longer use the `x`th 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 `10^9 + 7`.

### Examples

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

```
Input: words = ["abba","baab"], target = "bab"
Output: 4
Explanation: There are 4 ways to form target.
- index 0 (baab), index 1 (baab), index 2 (abba)
- index 0 (baab), index 1 (baab), index 3 (baab)
- index 0 (baab), index 2 (baab), index 3 (baab)
- 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` consist of only lowercase English letters.

## Solution

Reference implementation from [solution.py on GitHub](https://github.com/wislertt/leetcode-py/blob/main/leetcode/number_of_ways_to_form_a_target_string_given_a_dictionary/solution.py), full suite in [test\_solution.py](https://github.com/wislertt/leetcode-py/blob/main/leetcode/number_of_ways_to_form_a_target_string_given_a_dictionary/test_solution.py):

```python theme={"theme":{"light":"github-light","dark":"github-dark"}}
class Solution:
    # Time: O(S + n * m) where S = total chars in words, n = len(words[0]), m = len(target)
    # Space: O(26 * n + m)
    def num_ways(self, words: list[str], target: str) -> int:
        mod = 1_000_000_007
        n = len(words[0])
        m = len(target)

        counts: list[list[int]] = [[0] * 26 for _ in range(n)]
        for word in words:
            for k, char in enumerate(word):
                counts[k][ord(char) - 97] += 1

        dp = [0] * (m + 1)
        dp[0] = 1
        for k in range(n):
            column = counts[k]
            for i in range(m, 0, -1):
                freq = column[ord(target[i - 1]) - 97]
                if freq:
                    dp[i] = (dp[i] + dp[i - 1] * freq) % mod
        return dp[m]
```

## Complexity

| Time | Space |
| - | - |
| O(S + n \* m) where S = total chars in words, n = len(words\[0]), m = len(target) | O(26 \* n + m) |

## Tags

[NeetCode All](/catalog/neetcode).


This documentation is built and hosted on [Mintlify](https://mintlify.com), a developer documentation platform.