NeetCode #747LC-1639Hard2-D Dynamic Programming
← Back to All Problems#747 · #1639 · Number of Ways to Form a Target String Given a Dictionary(通过给定词典构造目标字符串的方案数)
📌 Problem Statement & Constraints
Given a list of equal-length words and a
target string, count the number of ways to form target by picking, for each position k, a column index that strictly increases and a character in that column equal to target[k]. Return the count modulo 1e9+7. Constraints: 1 <= words.length <= 1000, 1 <= words[i].length <= 1000, 1 <= target.length <= 1000, and all words have the same length.💡 Core Algorithmic Approaches
- Precompute
cnt[c][j], the number of words whosej-th column holds letterc. - Let
dp[i][j]be the number of ways to formtarget[:i]using only the firstjcolumns. - Either column
j-1is unused (dp[i][j-1]), or it suppliestarget[i-1]in one ofcnt[t][j-1]ways (dp[i-1][j-1] * cnt[t][j-1]). - Iterate
iover the target length andjover the columns, keeping only the previous target prefix.
💻 Benchmark Python3 Implementation
class Solution:
def numWays(self, words: List[str], target: str) -> int:
MOD = 10**9 + 7
m, W = len(target), len(words[0])
# cnt[c][j] = how many words have letter c in column j
cnt = [[0] * W for _ in range(26)]
for w in words:
for j, ch in enumerate(w):
cnt[ord(ch) - ord("a")][j] += 1
dp = [1] * (W + 1) # empty target: one way regardless of columns
for i in range(1, m + 1):
nxt = [0] * (W + 1)
t = ord(target[i - 1]) - ord("a")
for j in range(1, W + 1):
# skip column j-1, or use it for target[i-1]
nxt[j] = (nxt[j - 1] + dp[j - 1] * cnt[t][j - 1]) % MOD
dp = nxt
return dp[W]⚡ Complexity Deep Dive
⏱️ Time Complexity
O(m * W + total characters): building cnt scans the words, the DP is O(m * W).
💾 Space Complexity
O(26 * W): the column character counts.
⚠️ Interview Pitfalls & Follow-ups
- Choosing columns out of order: columns must be used in increasing index order, which the left-to-right DP enforces.
- Forgetting the skip term:
nxt[j] = nxt[j-1] + ...includes the option of not using columnj-1at all. - Multiplying by 1 instead of
cnt[t][j-1]: several words may supply the needed letter in that column, and each gives a distinct choice. - Reading
nxt[j-1]from the wrong layer: the running prefix must be within the current target position, not the previous one.
⚡
Test muscle memory on this topic via 3-Layer Flashcards
Active Recall: Mentally formulate Prompt ➔ Math Derivation ➔ Benchmark Implementation in 3 minutes.