0584HardArrayStringDynamic Programming

Ways to Punch a Code From Stencils

Tracked in this browser only

Trains the technique from

LeetCode 1639Number of Ways to Form a Target String Given a Dictionary

This is an original problem, written from a brief that listed the technique, the difficulty, the topics, the function shape and the input bounds — none of that problem's wording, examples, hints or editorials. The link is there so you can map your practice onto the standard set.

Same function shape, different story and different numbers.

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 is preloaded with this. It matches the parent problem's shape, so a solution that works here transfers to a judge unchanged.

Python

def num_ways(words: list[str], target: str) -> int:

Java

public int numWays(String[] words, String target)

The intended approach

Time O(w * L + L * m) — one sweep of the stencils plus one table update per column and code position.Space O(L * 26 + m) for the column tallies and the table.

Only two things matter about a column: which letters it can supply and how many stencils supply each of them. So build a per-column tally over the 26 letters in one sweep of the stencils. Then keep a table where entry `i` counts the runs that have already punched the first `i` letters of the code using columns strictly to the left of the column now being offered. Walk the columns from left to right, and inside a column walk the code positions from the highest down to 1, adding entry `i - 1` times that column's tally into entry `i`. Counting downward stops a single column from being credited twice inside one round. Entry `m` at the end is the answer.

Pythonentry point: num_ways

def num_ways(words, target):
    # O(w*L + L*m) time, O(L*26 + m) space, for w stencils of length L and a
    # code of length m: tally how many stencils show each letter in each column,
    # then run a table over the code positions. Sweeping columns left to right
    # and code positions downward inside each column means each column is offered
    # to each position at most once, which is what keeps the columns increasing.
    MOD = 1000000007
    width = len(words[0])
    m = len(target)
    if m > width:
        return 0
    tally = [[0] * 26 for _ in range(width)]
    for word in words:
        for j in range(width):
            tally[j][ord(word[j]) - 97] += 1
    table = [0] * (m + 1)
    table[0] = 1
    for j in range(width):
        top = m if m < j + 1 else j + 1
        for i in range(top, 0, -1):
            supply = tally[j][ord(target[i - 1]) - 97]
            if supply:
                table[i] = (table[i] + table[i - 1] * supply) % MOD
    return table[m]

The obvious version

Enumerate every strictly increasing choice of columns of the right size with combinations. For a fixed choice, the letters of the code are independent, so count the stencils supplying each required letter in its assigned column and multiply those counts. Adding the products over all choices gives the total.

This is not filler. It was written independently of the fast solution and the two were run against thousands of random inputs to confirm they agree — which is how the answer above is known to be right. Read it when the intended approach feels like a rabbit pulled out of a hat.

Python

def bf_num_ways(words, target):
    from itertools import combinations
    MOD = 1000000007
    width = len(words[0])
    m = len(target)
    if m > width:
        return 0
    total = 0
    for choice in combinations(range(width), m):
        product = 1
        for pos in range(m):
            column = choice[pos]
            letter = target[pos]
            supply = 0
            for word in words:
                if word[column] == letter:
                    supply += 1
            if supply == 0:
                product = 0
                break
            product *= supply
        total += product
    return total % MOD

How this problem was checked

Reference solution executed against 11 test cases — 11 passed
3 worked examples confirmed by running the code
0 eight-word sequences shared with the parent problem's text
Agrees with an independent brute-force implementation on random inputs
Test set proven to catch deliberately broken solutions
Reviewed by a separate quality pass
Function arity matches the parent problem's

Create a free account to unlock the solution

See the step-by-step animation, the intuition, and clean code in every language — free, no credit card.

Create a free account Already have an account? Sign in