Number of Ways to Form a Target String Given a Dictionary Solution
Number of Ways to Form a Target String Given a Dictionary solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript.
Number of Ways to Form a Target String Given a Dictionary is a hard coding problem on arrays, strings and dynamic programming, asked in Amazon and Google interviews.
- Difficulty: Hard
- Topics: Arrays, Strings, Dynamic Programming
- Asked at: Amazon, Google
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
You are given a list words of strings that all have the same length, and a string target. Build target one character at a time, from left to right, under these rules:
- To produce
target[i], pick the character at some indexkof any wordwords[j], providedwords[j][k] == target[i]. - Once index
kof any word has been used, every indexx <= kof every word becomes unusable for the rest of the process. - You may take several characters from the same word, as long as the rules above hold.
Return the number of ways to build target, modulo 10^9 + 7. Two ways differ when, for some i, target[i] came from a different word or a different index.
Example 1
Input: words = ["abc","bca"], target = "ac"
Output: 2
Explanation: The `a` must be index 0 of `"abc"`; the `c` is then index 1 of `"bca"` or index 2 of `"abc"`.
Example 2
Input: words = ["kai","kia","ika"], target = "ka"
Output: 8
Example 3
Input: words = ["ab"], target = "abc"
Output: 0
Explanation: The target is longer than the words.
Constraints
1 <= words.length <= 10001 <= words[i].length <= 1000all strings in words have the same length1 <= target.length <= 1000words[i] and target contain only lowercase English letters
Hints for Number of Ways to Form a Target String Given a Dictionary
Hint 1
The rule only cares about indices, not about which word: after using index
k, everything continues from indexk + 1in all words.Hint 2
So all that matters about column
kis how many words have each letter there. Precomputecnt[k][letter].Hint 3
Let
dp[i]be the number of ways to have builttarget[0..i)using columns seen so far. For each columnk, updatedp[i] += dp[i-1] · cnt[k][target[i-1]]withirunning downward (so each column is used at most once per way).
How to solve Number of Ways to Form a Target String Given a Dictionary
The words only matter through their columns: the process picks a strictly increasing sequence of column indices, one per target character, and at each picked column it can choose any word with the right letter there. So the count is a sum over increasing index sequences of products of per-column letter counts — a knapsack-style DP over columns.
Approach
- Count
cnt[k][c], the number of words whose letter at indexkisc. dp[0] = 1(the empty prefix), all otherdp[i] = 0.- For each column
kfrom left to right, forifrommin(t, k + 1)down to 1:dp[i] = (dp[i] + dp[i-1] · cnt[k][target[i-1]]) mod (10^9 + 7). - Return
dp[t].
Why it works
After processing columns 0..k, dp[i] counts the ways to build the first i target characters using only those columns. For column k, a way either does not use it (the old dp[i]) or uses it for target[i-1], after building target[0..i-1) from earlier columns (dp[i-1] before this column's update) times the number of words that offer that letter there. Iterating i downward guarantees the right-hand dp[i-1] is still the pre-column value.
Complexity
- Time —
O(L · t + total letters), with L the word length and t the target length - Space —
O(L · 26 + t)
Pitfalls
- Iterate
idownward within a column, or a single column could be used twice. dp[i-1] · cntcan reach about 10^12 before the modulus — multiply in 64 bits.- If the target is longer than the words, the answer is 0.
Reference solution
Python
from typing import List
def numWays(words: List[str], target: str) -> int:
MOD = 10 ** 9 + 7
m, t = len(words[0]), len(target)
cnt = [[0] * 26 for _ in range(m)]
for w in words:
for k, ch in enumerate(w):
cnt[k][ord(ch) - 97] += 1
dp = [0] * (t + 1)
dp[0] = 1
for k in range(m):
for i in range(min(t, k + 1), 0, -1):
c = cnt[k][ord(target[i - 1]) - 97]
if c:
dp[i] = (dp[i] + dp[i - 1] * c) % MOD
return dp[t]Java
public static int numWays(String[] words, String target) {
final long MOD = 1000000007L;
int m = words[0].length(), t = target.length();
int[][] cnt = new int[m][26];
for (String w : words) for (int k = 0; k < m; k++) cnt[k][w.charAt(k) - 'a']++;
long[] dp = new long[t + 1];
dp[0] = 1;
for (int k = 0; k < m; k++) {
for (int i = Math.min(t, k + 1); i >= 1; i--) {
int c = cnt[k][target.charAt(i - 1) - 'a'];
if (c > 0) dp[i] = (dp[i] + dp[i - 1] * c) % MOD;
}
}
return (int) dp[t];
}C++
int numWays(vector<string>& words, string target) {
const long long MOD = 1000000007LL;
int m = words[0].size(), t = target.size();
vector<array<int, 26>> cnt(m);
for (auto& row : cnt) row.fill(0);
for (auto& w : words) for (int k = 0; k < m; k++) cnt[k][w[k] - 'a']++;
vector<long long> dp(t + 1, 0);
dp[0] = 1;
for (int k = 0; k < m; k++) {
for (int i = min(t, k + 1); i >= 1; i--) {
int c = cnt[k][target[i - 1] - 'a'];
if (c > 0) dp[i] = (dp[i] + dp[i - 1] * c) % MOD;
}
}
return (int)dp[t];
}JavaScript
var numWays = function(words, target) {
var MOD = 1000000007, m = words[0].length, t = target.length;
var cnt = [];
for (var k = 0; k < m; k++) cnt.push(new Array(26).fill(0));
for (var w = 0; w < words.length; w++) {
for (var k = 0; k < m; k++) cnt[k][words[w].charCodeAt(k) - 97]++;
}
var dp = new Array(t + 1).fill(0);
dp[0] = 1;
for (var k = 0; k < m; k++) {
for (var i = Math.min(t, k + 1); i >= 1; i--) {
var c = cnt[k][target.charCodeAt(i - 1) - 97];
if (c) dp[i] = (dp[i] + dp[i - 1] * c) % MOD;
}
}
return dp[t];
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.