⚡Flashcard Drill➔
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

  1. Precompute cnt[c][j], the number of words whose j-th column holds letter c.
  2. Let dp[i][j] be the number of ways to form target[:i] using only the first j columns.
  3. Either column j-1 is unused (dp[i][j-1]), or it supplies target[i-1] in one of cnt[t][j-1] ways (dp[i-1][j-1] * cnt[t][j-1]).
  4. Iterate i over the target length and j over 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 column j-1 at 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.
🎯 Drill This Card Now➔

🧩 Related 2-D Dynamic Programming Problems