Number of Ways to Form a Target String Given

LeetCode 1639, Hard. Topics: Array, String, Dynamic Programming. View on LeetCode. Generate this problem as a practice environment: tested reference solution, 21 parametrized pytest cases, and a playground notebook:

lcpy gen -n 1639   # by problem number
lcpy gen -s number_of_ways_to_form_a_target_string_given_a_dictionary   # by problem name

Problem

You are given a list of strings of the same length words and a string target. Your task is to form target using the given words under the following rules:

target should be formed from left to right.
To form the ith character (0-indexed) of target, you can choose the kth character of the jth string in words if target[i] = words[j][k].
Once you use the kth character of the jth string of words, you can no longer use the xth character of any string in words where x <= k. In other words, all characters to the left of or at index k become unusuable for every string.
Repeat the process until you form the string target.

Notice that you can use multiple characters from the same string in words provided the conditions above are met. Return the number of ways to form target from words. Since the answer may be too large, return it modulo 10^9 + 7.

Examples

Input: words = ["acca","bbbb","caca"], target = "aba"
Output: 6
Explanation: There are 6 ways to form target.
- index 0 (acca), index 1 (bbbb), index 3 (caca)
- index 0 (acca), index 2 (bbbb), index 3 (caca)
- index 0 (acca), index 1 (bbbb), index 3 (acca)
- index 0 (acca), index 2 (bbbb), index 3 (acca)
- index 1 (caca), index 2 (bbbb), index 3 (acca)
- index 1 (caca), index 2 (bbbb), index 3 (caca)

Input: words = ["abba","baab"], target = "bab"
Output: 4
Explanation: There are 4 ways to form target.
- index 0 (baab), index 1 (baab), index 2 (abba)
- index 0 (baab), index 1 (baab), index 3 (baab)
- index 0 (baab), index 2 (baab), index 3 (baab)
- index 1 (abba), index 2 (baab), index 3 (baab)

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 consist of only lowercase English letters.

Solution

Reference implementation from solution.py on GitHub, full suite in test_solution.py:

class Solution:
    # Time: O(S + n * m) where S = total chars in words, n = len(words[0]), m = len(target)
    # Space: O(26 * n + m)
    def num_ways(self, words: list[str], target: str) -> int:
        mod = 1_000_000_007
        n = len(words[0])
        m = len(target)

        counts: list[list[int]] = [[0] * 26 for _ in range(n)]
        for word in words:
            for k, char in enumerate(word):
                counts[k][ord(char) - 97] += 1

        dp = [0] * (m + 1)
        dp[0] = 1
        for k in range(n):
            column = counts[k]
            for i in range(m, 0, -1):
                freq = column[ord(target[i - 1]) - 97]
                if freq:
                    dp[i] = (dp[i] + dp[i - 1] * freq) % mod
        return dp[m]

Complexity

Time	Space
O(S + n * m) where S = total chars in words, n = len(words[0]), m = len(target)	O(26 * n + m)

Welcome

Getting Started

Practice

CLI

Catalog

Contributing

Troubleshooting

Number of Ways to Form a Target String Given

Problem

Examples

Constraints

Solution

Complexity

Tags

​Problem

​Examples

​Constraints

​Solution

​Complexity

​Tags

Problem

Examples

Constraints

Solution

Complexity

Tags