Ways to Assemble a Target from Candidate Columns
A decoder must spell a target string by picking one character per step from equal-length candidate strings, always advancing the column index. Count the distinct ways to assemble the target.
Problem
Given a list words of strings all of the same length and a string target, count the ways to form target by choosing characters: to append target[i] you pick some word's character at a column k strictly greater than the column used for target[i-1]; once a column is used for one character it cannot be reused for any later character. Return the count modulo 1e9 + 7.
Input
A list words of equal-length lowercase strings and a string target.
Output
An integer: the number of ways modulo 1e9 + 7.
Constraints
- 1 <= words.length <= 1000
- 1 <= words[i].length <= 1000 (all equal); 1 <= target.length <= 1000
- target.length <= words[i].length.
Examples
Example 1
Input
words = ["acca","bbbb","caca"], target = "aba"
Output
6
There are 6 valid column selections spelling 'aba'.
Example 2
Input
words = ["abba","baab"], target = "bab"
Output
4
Four ways to pick increasing columns spelling 'bab'.