Solution: Number of Ways to Form Target String Given a Dictionary

Explore how to solve the problem of counting the number of ways to form a target string from a list of words using dynamic programming. Understand building a frequency table of characters by columns and updating counts of possible prefixes to efficiently compute the total ways to form the target string. Gain insights into the time and space complexity involved in the solution.

We'll cover the following...

Statement
Solution
- Time complexity
- Space complexity

Statement

You are given a list of $n$ strings, words, where each string has the same length $m$ , and a target string, target, of length $t$ . A target can be formed using the given words under the following rules:

You must build the target from left to right.
To form the i^th character (0-indexed) of target, you can choose any k^th character of any j^th string in words, i.e., target[i] = words[j][k].
Once you use the k^th character of the j^th string in words, your next letter can't be a character from index $0$ through k of any string in words. In simple words, all characters to the left of or at index k become unusable for every string, and the next letter must come from positions strictly to the right of k.
Repeat the process until you’ve formed the complete target.

Note: You can use multiple characters from the same string in words, as long as the rules above are followed.

Your task is to find and return the number of ways to form the string target from words. As the answer might be too large, return it modulo $10^{9} + 7$ .

Constraints:

$1 \leq$ words.length $\leq 1000$
$1 \leq$ ...