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

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 ith character (0-indexed) of target, you can choose any kth character of any jth string in words, i.e., target[i] = words[j][k].

• Once you use the kth character of the jth 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$ words[i].length $\leq 1000$

• All strings in words have the same length.

• $1 \leq$ target.length $\leq 1000$

• words[i] and target contain only lowercase English letters.

Solution

As all words have the same length, placing them one under another creates a word grid where each column contains characters from the same position in each word. This helps to quickly find how many times a certain character appears at a specific position across all words.