Show problems as
Classic problem #1639HardArrayStringDynamic Programming

Number of Ways to Form a Target String Given a Dictionary

Real-world version: Ways to Punch a Code From Stencils
Tracked in this browser only
Read Number of Ways to Form a Target String Given a Dictionary on LeetCode(opens in a new tab)

The statement here is our own: the same inputs, outputs and technique.

A workshop owns a set of stencils listed in words. Every stencil is the same width and carries one lowercase letter in each of its columns, numbered from 0.

The code target has to be punched out letter by letter, from its first letter to its last. To punch one letter you name a stencil and a column of it that shows that letter. The rail advances after every punch, so each letter of the code must be taken from a column strictly to the right of the column used for the letter before it. Column numbers are shared across stencils, and stencils may be swapped in and out freely between punches.

Two runs count as different when they name a different column for some letter of the code, and also when they name a different stencil for some letter of the code. Return how many different runs punch out the whole code, taken modulo 1000000007.

Examples

Example 1

Input
words = ["abc", "abc", "abc"], target = "ac"
Output
9

The letter a is only in column 0 and the letter c only in column 2, so every run uses those two columns. Each punch can name any of the three stencils, which gives three choices for a and three for c.

Example 2

Input
words = ["ab", "cd"], target = "ac"
Output
0

The letter c appears only in column 0, and column 0 cannot come after the column used for a, so the code cannot be punched at all.

Example 3

Input
words = ["aaaa"], target = "aa"
Output
6

There is one stencil and it shows a in all four columns, so a run is fixed by which two columns it uses, in increasing order, and there are six such choices.

Constraints

  • 1 <= words.length <= 1000
  • 1 <= words[i].length <= 1000
  • Every stencil in words has the same width.
  • 1 <= target.length <= 1000
  • words[i] and target hold lowercase English letters only.
  • Return the count taken modulo 1000000007, so the answer is below 1000000007.

The signature

The editor starts with this. It matches the parent problem's shape, so a solution that works here works on a standard judge unchanged.

Python
def num_ways(words: list[str], target: str) -> int:
Java
public int numWays(String[] words, String target)

More on the same topics