Number of Ways to Form a Target String Given a Dictionary
Number of Ways to Form a Target String Given a Dictionary is a hard dynamic programming problem solved with the strings pattern.
The best approach, optimal (column letter counts + 1d dp), runs in O(W · m + m · t) time and O(26 · m + t) space.
Below are 2 approaches in Java, Python, C++ and JavaScript, from brute force (try every word at every column) up.
Problem
You are given a list words where every string has the same length, and a string target. Build target from left to right: each character target[i] must be picked from some word at some column k, and every later character must use a column strictly to the right of k. Once column k has been used, no column at or before k can be used again, in any word.
Different choices of word or column count as different ways, and several characters may come from the same word. Return the number of ways to build target, modulo 10^9 + 7.
Examples
Example 1
- Input
words = ["abca", "bacb"], target = "ab"- Output
3- Why
- Take 'a' from column 0 and 'b' from column 1 or 3 (2 ways), or 'a' from column 1 and 'b' from column 3 (1 way).
Example 2
- Input
words = ["xyz", "yxz"], target = "xz"- Output
4- Why
- 'x' can come from column 0 or 1 (one word each), and 'z' from column 2 in either word: 2 × 2 = 4.
Example 3
- Input
words = ["aa", "aa"], target = "aaa"- Output
0- Why
- Each character needs its own, strictly later column, but there are only 2 columns for 3 characters.
Constraints
1 <= words.length <= 10001 <= words[i].length <= 1000, and all words have the same length.1 <= target.length <= 1000words[i]andtargetcontain only lowercase English letters.- Return the answer modulo
10^9 + 7.
Solve it here
Write your solution in Java, Python, C++ or JavaScript and run it against the examples, right in the page. Submit runs the hidden tests too and, with a free account, records the solve in your revision log.
Your own testcases: Run checks these, and the expected output comes from our reference solution.
My submissions
Nothing yet. Every Run and Submit you make while signed in shows up here.
| When | Result | Tests | Runtime | Your time | Type |
|---|
Run checks the testcases above (3 examples, or your own). Submit also runs 11 hidden tests and saves the solve to your log. Signed in, every Run and Submit is saved under My submissions; your draft stays in this browser.
Solutions
Try it yourself first. Then compare: each approach lists its idea, the steps, its time and space, and the code in Java, Python, C++ and JavaScript.
| Approach | Time | Space |
|---|---|---|
| Brute force (try every word at every column) | O(2^m · W) in the worst case | O(m) |
| Optimal (column letter counts + 1D DP) | O(W · m + m · t) | O(26 · m + t) |
1Brute force (try every word at every column)
O(2^m · W) in the worst caseWithout memoisation the same (i, k) states are recomputed over and over; m is the word length and W the number of words.O(m)The recursion depth is at most the word length.Recursively decide, for the current target position i and column k, whether to skip column k or to take target[i] from column k of any word that has it there. Every combination is enumerated separately.
- ways(i, k): if i == target.length return 1; if k == word length return 0.
- Start with ways(i, k + 1) (skip this column).
- For each word whose letter at k equals target[i], add ways(i + 1, k + 1).
- Return the total modulo 10^9 + 7.
class Solution {
private static final int MOD = 1_000_000_007;
public int numWays(String[] words, String target) {
return (int) ways(words, target, 0, 0);
}
private long ways(String[] words, String target, int i, int k) {
if (i == target.length()) return 1;
if (k == words[0].length()) return 0;
long total = ways(words, target, i, k + 1);
for (String w : words) {
if (w.charAt(k) == target.charAt(i)) {
total = (total + ways(words, target, i + 1, k + 1)) % MOD;
}
}
return total;
}
}class Solution:
def numWays(self, words: List[str], target: str) -> int:
MOD = 1_000_000_007
m, t = len(words[0]), len(target)
def ways(i: int, k: int) -> int:
if i == t:
return 1
if k == m:
return 0
total = ways(i, k + 1)
for w in words:
if w[k] == target[i]:
total = (total + ways(i + 1, k + 1)) % MOD
return total
return ways(0, 0)class Solution {
static const int MOD = 1000000007;
long long ways(vector<string>& words, const string& target, int i, int k) {
if (i == (int)target.size()) return 1;
if (k == (int)words[0].size()) return 0;
long long total = ways(words, target, i, k + 1);
for (const string& w : words) {
if (w[k] == target[i]) {
total = (total + ways(words, target, i + 1, k + 1)) % MOD;
}
}
return total;
}
public:
int numWays(vector<string>& words, string target) {
return (int)ways(words, target, 0, 0);
}
};function numWays(words, target) {
const MOD = 1000000007;
const m = words[0].length, t = target.length;
function ways(i, k) {
if (i === t) return 1;
if (k === m) return 0;
let total = ways(i, k + 1);
for (const w of words) {
if (w[k] === target[i]) {
total = (total + ways(i + 1, k + 1)) % MOD;
}
}
return total;
}
return ways(0, 0);
}2Optimal (column letter counts + 1D DP)
O(W · m + m · t)Counting reads every character of every word once; the DP does t updates per column.O(26 · m + t)The count table has 26 entries per column and dp has t + 1 entries.Count how many words have each letter in each column. Then sweep the columns left to right with dp[i] = number of ways to have built the first i target characters so far. At column k, every state i can extend to i + 1 in count[k][target[i]] ways. Updating i from high to low keeps each column from being used twice.
- Build count[k][c] for every column k and letter c.
- dp = [1, 0, 0, ..., 0] of size t + 1.
- For each column k: for i from min(t - 1, k) down to 0, dp[i + 1] += dp[i] * count[k][target[i]] (mod 10^9 + 7).
- Return dp[t].
class Solution {
public int numWays(String[] words, String target) {
final long MOD = 1_000_000_007L;
int m = words[0].length(), t = target.length();
int[][] count = new int[m][26];
for (String w : words) {
for (int k = 0; k < m; k++) count[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 - 1, k); i >= 0; i--) {
int c = count[k][target.charAt(i) - 'a'];
if (c > 0) dp[i + 1] = (dp[i + 1] + dp[i] * c) % MOD;
}
}
return (int) dp[t];
}
}class Solution:
def numWays(self, words: List[str], target: str) -> int:
MOD = 1_000_000_007
m, t = len(words[0]), len(target)
count = [[0] * 26 for _ in range(m)]
for w in words:
for k, ch in enumerate(w):
count[k][ord(ch) - 97] += 1
tgt = [ord(ch) - 97 for ch in target]
dp = [0] * (t + 1)
dp[0] = 1
for k in range(m):
col = count[k]
for i in range(min(t - 1, k), -1, -1):
c = col[tgt[i]]
if c:
dp[i + 1] = (dp[i + 1] + dp[i] * c) % MOD
return dp[t]class Solution {
public:
int numWays(vector<string>& words, string target) {
const long long MOD = 1000000007LL;
int m = words[0].size(), t = target.size();
vector<array<int, 26>> count(m);
for (auto& col : count) col.fill(0);
for (const string& w : words) {
for (int k = 0; k < m; k++) count[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 - 1, k); i >= 0; i--) {
int c = count[k][target[i] - 'a'];
if (c > 0) dp[i + 1] = (dp[i + 1] + dp[i] * c) % MOD;
}
}
return (int)dp[t];
}
};function numWays(words, target) {
const MOD = 1000000007;
const m = words[0].length, t = target.length;
const count = Array.from({ length: m }, () => new Array(26).fill(0));
for (const w of words) {
for (let k = 0; k < m; k++) count[k][w.charCodeAt(k) - 97]++;
}
const dp = new Array(t + 1).fill(0);
dp[0] = 1;
for (let k = 0; k < m; k++) {
for (let i = Math.min(t - 1, k); i >= 0; i--) {
const c = count[k][target.charCodeAt(i) - 97];
// dp[i] * c stays below 2^53, so plain numbers are exact
if (c > 0) dp[i + 1] = (dp[i + 1] + dp[i] * c) % MOD;
}
}
return dp[t];
}Edge cases to test
- target is longer than the word length: answer 0
- A target letter that never appears in any word
- All words identical, so each column contributes a multiplicity of words.length
- Large counts that overflow 32-bit integers before taking the modulo
Hints
Hint 1
Which word a letter comes from only matters through how many words have that letter in that column. Precompute count[column][letter].
Hint 2
Let dp[i][k] be the number of ways to build the first i target characters using only columns before k. At column k you either skip it or use it for target[i].
Hint 3
Using column k for target[i] contributes dp[i][k] × count[k][target[i]]. You only need one row of dp if you update i from right to left.
FAQ
What is the best time complexity for Number of Ways to Form a Target String Given a Dictionary?
Optimal (column letter counts + 1D DP) runs in O(W · m + m · t) time and O(26 · m + t) extra space. Counting reads every character of every word once; the DP does t updates per column.
Which pattern does Number of Ways to Form a Target String Given a Dictionary use?
It is a dynamic programming problem that uses the strings pattern. Other problems with the same pattern: Edit Distance, Longest Common Subsequence, Longest Palindromic Subsequence.
Is there a brute force solution for Number of Ways to Form a Target String Given a Dictionary?
Yes. Brute force (try every word at every column) takes O(2^m · W) in the worst case time and O(m) space. Recursively decide, for the current target position i and column k, whether to skip column k or to take target[i] from column k of any word that has it there.
Which edge cases should I test for Number of Ways to Form a Target String Given a Dictionary?
target is longer than the word length: answer 0; A target letter that never appears in any word; All words identical, so each column contributes a multiplicity of words.length; Large counts that overflow 32-bit integers before taking the modulo.