Number of Ways to Form a Target String Given a Dictionary
Asked at Uber
Problem
Given a dictionary of words and a target string, count the number of ways to form the target by picking exactly one character from each word in order across all words. Characters are picked column by column (all words contribute one character per column), and you can skip picking a character from any word. Return the count modulo 10^9+7.
Asked At
| Company | Difficulty | |
|---|---|---|
| Uber | HARD | View all Uber questions → |
How to Think About It
Count frequency of each character in each column of the dictionary
DP[i][j] = ways to form target[0..i] using first j columns
Base case: DP[-1][j] = 1 for all j (empty target has one way)
Transition: either skip column j (DP[i][j-1]) or use it (DP[i-1][j-1] * freq[target[i]][j])
Space optimize by rolling over columns since transitions only look at j-1
Optimal Approach
Precompute freq[c][j] = count of character c in column j across all words. Use DP where dp[i][j] represents ways to form target[0..i] using first j columns. For each state, either skip column j (carry dp[i][j-1] forward) or use it to contribute target[i] (add dp[i-1][j-1] * freq[target[i]][j]). Space optimize with a 1D array over columns.
What Trips People Up in Real Interviews
Clarify: you pick at most one character per column from all words combined
Key insight: columns are independent — each column contributes a character or nothing
Precompute character frequencies per column to avoid recomputation
Watch for overflow — use modulo at every addition/multiplication
Edge case: if target length exceeds word length, answer is 0
Solution Code
class Solution:
def numWays(self, words: list[str], target: str) -> int:
MOD = 10**9 + 7
m, n = len(target), len(words[0])
freq = [[0] * n for _ in range(26)]
for word in words:
for j, ch in enumerate(word):
freq[ord(ch) - ord('a')][j] += 1
dp = [0] * (m + 1)
dp[0] = 1
for j in range(n):
for i in range(m - 1, -1, -1):
dp[i + 1] = (dp[i + 1] + dp[i] * freq[ord(target[i]) - ord('a')][j]) % MOD
return dp[m]Frequently Asked Questions
What is the Number of Ways to Form a Target String Given a Dictionary problem?
Given a dictionary of words and a target string, count the number of ways to form the target by picking exactly one character from each word in order across all words. Characters are picked column by column (all words contribute one character per column), and you can skip picking a character from any word. Return the count modulo 10^9+7.
How do you solve Number of Ways to Form a Target String Given a Dictionary?
The optimal approach is described in detail above, including step-by-step walkthroughs, complexity analysis, and solution code in Python. Scroll up to the "Optimal Approach" section.
What companies ask Number of Ways to Form a Target String Given a Dictionary?
Number of Ways to Form a Target String Given a Dictionary is asked at Uber. It is a hard difficulty problem.
What are common mistakes on Number of Ways to Form a Target String Given a Dictionary?
- Clarify: you pick at most one character per column from all words combined
- Key insight: columns are independent — each column contributes a character or nothing
- Precompute character frequencies per column to avoid recomputation
- Watch for overflow — use modulo at every addition/multiplication
- Edge case: if target length exceeds word length, answer is 0