LeetCode Problem Workspace
Number of Ways to Form a Target String Given a Dictionary
Calculate the number of ways to form a target string using words of equal length via state transition dynamic programming.
3
Topics
5
Code langs
3
Related
Practice Focus
Hard · State transition dynamic programming
Answer-first summary
Calculate the number of ways to form a target string using words of equal length via state transition dynamic programming.
Ace coding interviews with Interview AiBoxInterview AiBox guidance for State transition dynamic programming
Use dynamic programming to track the number of ways to form each prefix of the target. Precompute character frequencies at each index across all words to enable constant-time lookups. Iterate through the target and update the DP array, ensuring each state reflects all valid combinations while maintaining modular arithmetic for large outputs.
Problem Statement
Given a list of strings words where each string has the same length, and a target string, count the total ways to form target using characters from words. You can pick the i-th character from any string at position i, but characters must match the corresponding target position.
Form target by selecting one character from each position across words while following index order. Multiple characters from the same word can be used as long as each choice respects the target alignment. Return the total number of distinct ways to achieve the target modulo 10^9 + 7.
Examples
Example 1
Input: words = ["acca","bbbb","caca"], target = "aba"
Output: 6
There are 6 ways to form target. "aba" -> index 0 ("acca"), index 1 ("bbbb"), index 3 ("caca") "aba" -> index 0 ("acca"), index 2 ("bbbb"), index 3 ("caca") "aba" -> index 0 ("acca"), index 1 ("bbbb"), index 3 ("acca") "aba" -> index 0 ("acca"), index 2 ("bbbb"), index 3 ("acca") "aba" -> index 1 ("caca"), index 2 ("bbbb"), index 3 ("acca") "aba" -> index 1 ("caca"), index 2 ("bbbb"), index 3 ("caca")
Example 2
Input: words = ["abba","baab"], target = "bab"
Output: 4
There are 4 ways to form target. "bab" -> index 0 ("baab"), index 1 ("baab"), index 2 ("abba") "bab" -> index 0 ("baab"), index 1 ("baab"), index 3 ("baab") "bab" -> index 0 ("baab"), index 2 ("baab"), index 3 ("baab") "bab" -> 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 contain only lowercase English letters.
Solution Approach
Precompute character frequencies per index
For each column in words, count how many times each character appears. This frequency table allows the DP transition to quickly determine how many ways a target character can be chosen at that index without scanning all words repeatedly.
Dynamic programming state definition
Define dp[i] as the number of ways to form the first i characters of target. Iterate through each position j in words, updating dp[i] by adding dp[i-1] * frequency of target[i-1] at index j. This captures all valid transitions efficiently.
Iterate and update with modular arithmetic
Process target characters sequentially. For each target character at position i, update dp[i] using the frequency table from each index j. Apply modulo 10^9 + 7 after each addition to prevent overflow and maintain correctness for large inputs.
Complexity Analysis
| Metric | Value |
|---|---|
| Time | O(wordLength \cdot targetLength + wordLength \cdot totalWords) |
| Space | O(wordLength) |
Time 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.
What Interviewers Usually Probe
- Notice if the candidate attempts brute force, highlighting inefficiency in handling large word lists.
- Look for correct use of precomputed frequency tables to optimize character lookup at each index.
- Confirm that the DP state accurately represents prefix completions of the target string.
Common Pitfalls or Variants
Common pitfalls
- Forgetting to handle modular arithmetic and producing incorrect large-number outputs.
- Confusing word indices and target indices, resulting in invalid character selections.
- Overwriting DP states prematurely instead of iterating backwards or using temporary arrays for updates.
Follow-up variants
- Limit word lengths to small sizes, focusing on memory-efficient DP optimizations.
- Allow repeated characters in target to test handling of multiple paths using the same words.
- Change constraints to include uppercase letters, requiring adjustments in frequency tables.
FAQ
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.
Solution
Solution 1: Preprocessing + Memory Search
We noticed that the length of each string in the string array $words$ is the same, so let's remember $n$, then we can preprocess a two-dimensional array $cnt$, where $cnt[j][c]$ represents the string array $words$ The number of characters $c$ in the $j$-th position of.
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)Solution 2: Preprocessing + Dynamic Programming
Similar to Solution 1, we can first preprocess a two-dimensional array $cnt$, where $cnt[j][c]$ represents the number of characters $c$ in the $j$-th position of the string array $words$.
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)Continue Topic
array
Practice more edge cases under the same topic.
arrow_forwardauto_awesomeContinue Pattern
State transition dynamic programming
Expand the same solving frame across more problems.
arrow_forwardsignal_cellular_altSame Difficulty Track
Hard
Stay on this level to stabilize interview delivery.
arrow_forward