Statementâ–¼
You are given a list of words
, where each string has the same length target
, of length 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) oftarget
, you can choose anyk
th
character of anyj
th
string inwords
, i.e.,target[i] = words[j][k]
.Once you use the
k
th
character of thej
th
string inwords
, your next letter can't be a character from index0 throughk
of any string inwords
. 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 ofk
.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Â
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.
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.