Number of Ways to Form a Target String Given a Dictionary

Hard
1514.

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 coding problem on arrays, strings and dynamic programming, asked in Amazon and Google interviews.

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 index k of any word words[j], provided words[j][k] == target[i].
  • Once index k of any word has been used, every index x <= k of 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 <= 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
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {string[]} words
 * @param {string} target
 * @return {number}
 */
var numWays = function(words, target) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

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.

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 index k of any word words[j], provided words[j][k] == target[i].
  • Once index k of any word has been used, every index x <= k of 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 <= 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

Hints for Number of Ways to Form a Target String Given a Dictionary

  1. Hint 1

    The rule only cares about indices, not about which word: after using index k, everything continues from index k + 1 in all words.

  2. Hint 2

    So all that matters about column k is how many words have each letter there. Precompute cnt[k][letter].

  3. Hint 3

    Let dp[i] be the number of ways to have built target[0..i) using columns seen so far. For each column k, update dp[i] += dp[i-1] · cnt[k][target[i-1]] with i running 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

  1. Count cnt[k][c], the number of words whose letter at index k is c.
  2. dp[0] = 1 (the empty prefix), all other dp[i] = 0.
  3. For each column k from left to right, for i from min(t, k + 1) down to 1: dp[i] = (dp[i] + dp[i-1] · cnt[k][target[i-1]]) mod (10^9 + 7).
  4. 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 i downward within a column, or a single column could be used twice.
  • dp[i-1] · cnt can 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.

All 1199 arrays problems · the whole catalogue

Learn the technique: Arrays · Strings