What is the key pattern used in Number of Ways to Form a Target String Given a Dictionary?

The primary pattern is state transition dynamic programming, where each DP state represents the number of ways to form target prefixes.

How do you efficiently count valid character choices at each position?

Precompute a frequency table for each column in words, which allows constant-time access to how many times each target character occurs.

Can the same word provide multiple characters for forming target?

Yes, multiple characters from the same word can be used, as long as each character aligns with the target index in order.

What is the time complexity of this DP approach?

The algorithm runs in O(wordLength * targetLength + wordLength * totalWords), accounting for frequency computation and DP updates.

How do you prevent integer overflow in this problem?

Apply modulo 10^9 + 7 after every DP update to keep all counts within integer limits.

#1639

Hard

auto_awesome状态·转移·动态规划

LeetCode 题解工作台

通过给定词典构造目标字符串的方案数

给你一个字符串列表 words 和一个目标字符串 target 。 words 中所有字符串都长度相同。你的目标是使用给定的 words 字符串列表按照下述规则构造 target ：从左到右依次构造 target 的每一个字符。为了得到 target 第 i 个字符（下标从 0 开始），当…

数组字符串动态规划

题目描述

给你一个字符串列表 words 和一个目标字符串 target 。words 中所有字符串都 长度相同 。

你的目标是使用给定的 words 字符串列表按照下述规则构造 target ：

从左到右依次构造 target 的每一个字符。
为了得到 target 第 i 个字符（下标从 0 开始），当 target[i] = words[j][k] 时，你可以使用 words 列表中第 j 个字符串的第 k 个字符。
一旦你使用了 words 中第 j 个字符串的第 k 个字符，你不能再使用 words 字符串列表中任意单词的第 x 个字符（x <= k）。也就是说，所有单词下标小于等于 k 的字符都不能再被使用。
请你重复此过程直到得到目标字符串 target 。

请注意，在构造目标字符串的过程中，你可以按照上述规定使用 words 列表中 同一个字符串 的 多个字符 。

请你返回使用 words 构造 target 的方案数。由于答案可能会很大，请对 10⁹ + 7 取余后返回。

（译者注：此题目求的是有多少个不同的 k 序列，详情请见示例。）

示例 1：

输入：words = ["acca","bbbb","caca"], target = "aba"
输出：6
解释：总共有 6 种方法构造目标串。
"aba" -> 下标为 0 ("acca")，下标为 1 ("bbbb")，下标为 3 ("caca")
"aba" -> 下标为 0 ("acca")，下标为 2 ("bbbb")，下标为 3 ("caca")
"aba" -> 下标为 0 ("acca")，下标为 1 ("bbbb")，下标为 3 ("acca")
"aba" -> 下标为 0 ("acca")，下标为 2 ("bbbb")，下标为 3 ("acca")
"aba" -> 下标为 1 ("caca")，下标为 2 ("bbbb")，下标为 3 ("acca")
"aba" -> 下标为 1 ("caca")，下标为 2 ("bbbb")，下标为 3 ("caca")

示例 2：

输入：words = ["abba","baab"], target = "bab"
输出：4
解释：总共有 4 种不同形成 target 的方法。
"bab" -> 下标为 0 ("baab")，下标为 1 ("baab")，下标为 2 ("abba")
"bab" -> 下标为 0 ("baab")，下标为 1 ("baab")，下标为 3 ("baab")
"bab" -> 下标为 0 ("baab")，下标为 2 ("baab")，下标为 3 ("baab")
"bab" -> 下标为 1 ("abba")，下标为 2 ("baab")，下标为 3 ("baab")

示例 3：

输入：words = ["abcd"], target = "abcd"
输出：1

示例 4：

输入：words = ["abab","baba","abba","baab"], target = "abba"
输出：16

提示：

1 <= words.length <= 1000
1 <= words[i].length <= 1000
words 中所有单词长度相同。
1 <= target.length <= 1000
words[i] 和 target 都仅包含小写英文字母。

lightbulb

解题思路

方法一：预处理 + 记忆化搜索

我们注意到，字符串数组 $words$ 中的每一个字符串长度都相同，不妨记为 $n$ ，那么我们可以预处理出一个二维数组 $cnt$ ，其中 $cnt[j][c]$ 表示字符串数组 $words$ 中第 $j$ 个位置的字符 $c$ 的数量。

接下来，我们设计一个函数 $dfs(i, j)$ ，表示构造 $target[i,..]$ 且当前从 $words$ 中选取的字符位置为 $j$ 的方案数。那么答案就是 $dfs(0, 0)$ 。

函数 $dfs(i, j)$ 的计算逻辑如下：

如果 $i \geq m$ ，说明 $target$ 中的所有字符都已经被选取，那么方案数为 $1$ 。
如果 $j \geq n$ ，说明 $words$ 中的所有字符都已经被选取，那么方案数为 $0$ 。
否则，我们可以不选择 $words$ 中的第 $j$ 个位置的字符，那么方案数为 $dfs(i, j + 1)$ ；或者我们选择 $words$ 中的第 $j$ 个位置的字符，那么方案数为 $dfs(i + 1, j + 1) \times cnt[j][target[i] - 'a']$ 。

最后，我们返回 $dfs(0, 0)$ 即可。注意答案的取模操作。

时间复杂度 $O(m \times n)$ ，空间复杂度 $O(m \times n)$ 。其中 $m$ 为字符串 $target$ 的长度，而 $n$ 为字符串数组 $words$ 中每个字符串的长度。

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

class Solution:
    def numWays(self, words: List[str], target: str) -> int:
        @cache
        def dfs(i: int, j: int) -> int:
            if i >= m:
                return 1
            if j >= n:
                return 0
            ans = dfs(i + 1, j + 1) * cnt[j][ord(target[i]) - ord('a')]
            ans = (ans + dfs(i, j + 1)) % mod
            return ans

        m, n = len(target), len(words[0])
        cnt = [[0] * 26 for _ in range(n)]
        for w in words:
            for j, c in enumerate(w):
                cnt[j][ord(c) - ord('a')] += 1
        mod = 10**9 + 7
        return dfs(0, 0)

speed

复杂度分析

指标	值
时间	complexity is O(wordLength * targetLength + wordLength * totalWords) due to building frequency tables and updating DP states. Space complexity is O(wordLength) to store DP array and temporary frequency counts.
空间	O(wordLength)

psychology

面试官常问的追问

外企场景

question_mark
Notice if the candidate attempts brute force, highlighting inefficiency in handling large word lists.
question_mark
Look for correct use of precomputed frequency tables to optimize character lookup at each index.
question_mark
Confirm that the DP state accurately represents prefix completions of the target string.

warning

常见陷阱

外企场景

error
Forgetting to handle modular arithmetic and producing incorrect large-number outputs.
error
Confusing word indices and target indices, resulting in invalid character selections.
error
Overwriting DP states prematurely instead of iterating backwards or using temporary arrays for updates.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Limit word lengths to small sizes, focusing on memory-efficient DP optimizations.
arrow_right_alt
Allow repeated characters in target to test handling of multiple paths using the same words.
arrow_right_alt
Change constraints to include uppercase letters, requiring adjustments in frequency tables.

help

常见问题

外企场景

继续练习

#1578 使绳子变成彩色的最短时间 #2019 解出数学表达式的学生分数 #1255 得分最高的单词集合