Number of Ways to Form a Target String Given a Dictionary

Step 1: Only the columns matter, not the words

When we take a character from column col, it does not matter which word it came from, only how many words offer that letter there. So first count, for every column, how many words have each letter: count[col][letter].

Step 2: Define the subproblem

Let ways[j] be the number of ways to form the first j characters of target using only the columns processed so far. Before any column, ways[0] = 1 (the empty prefix) and all others are 0.

Step 3: Process one column at a time

For a new column col, each prefix length j can be reached in two ways:

• skip the column: the old ways[j] stays;
• use the column for character j: extend any way of forming j - 1 characters, choosing one of the count[col][target[j - 1]] words that have the right letter here.

ways[j] = ways[j] + ways[j - 1] × count[col][target[j - 1]]

Step 4: Go through j backwards

Updating j from high to low makes sure ways[j - 1] still holds the value from before this column, so a column is never used twice for the same way. This is the same trick as in the 0/1 knapsack problem.

words = ["abba", "baab"], target = "bab". The column counts are: column 0 has a: 1, b: 1; column 1 has b: 1, a: 1; column 2 has b: 1, a: 1; column 3 has a: 1, b: 1.

The answer is ways[3] = 4.

The inner loop starts at min(m, col + 1), because after col + 1 columns, at most col + 1 characters can have been formed.

public class NumberOfWaysToFormTargetString {

    private static final int MOD = 1_000_000_007;

    public static int numWays(String[] words, String target) {
        int len = words[0].length();
        int m = target.length();
        int[][] count = new int[len][26];     // count[col][c]: words with letter c in column col
        for (String w : words) {
            for (int col = 0; col < len; col++) {
                count[col][w.charAt(col) - 'a']++;
            }
        }
        // ways[j]: ways to build the first j letters of target using the columns seen so far
        long[] ways = new long[m + 1];
        ways[0] = 1;
        for (int col = 0; col < len; col++) {
            for (int j = Math.min(m, col + 1); j >= 1; j--) {   // backwards: use col once
                int c = target.charAt(j - 1) - 'a';
                ways[j] = (ways[j] + ways[j - 1] * count[col][c]) % MOD;
            }
        }
        return (int) ways[m];
    }

    public static void main(String[] args) {
        System.out.println(numWays(new String[] {"acca", "bbbb", "caca"}, "aba"));   // 6
        System.out.println(numWays(new String[] {"abba", "baab"}, "bab"));           // 4
    }
}

• Time: O(w × L + L × m), where w is the number of words, L their length and m the target's length: counting, then the table.
• Space: O(26 × L + m).

Processing items one at a time and updating a one-dimensional table backwards is the same pattern as in Target Sum.