Number of Ways to Form a Target String Given a Dictionary

Problem

You are given a list of strings of the same length words and a string target.

Your task is to form target using the given words under the following rules:

target should be formed from left to right.
To form the ith character (0-indexed) of target, you can choose the kth character of the jth string in words if target[i] = words[j][k].
Once you use the kth character of the jth string of words, you can no longer use the xth character of any string in words where x <= k. In other words, all characters to the left of or at index k become unusuable for every string.
Repeat the process until you form the string target.

Notice that you can use multiple characters from the same string in words provided the conditions above are met.

Return the number of ways to form target from words. Since the answer may be too large, return it modulo 10^9 + 7.

Examples

Example 1:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11


Input:
words = ["acca","bbbb","caca"], target = "aba"
Output:
 6
Explanation: There are 6 ways to form target.
"aba" -> index 0 ("acca"), index 1 ("bbbb"), index 3 ("caca")
"aba" -> index 0 ("acca"), index 2 ("bbbb"), index 3 ("caca")
"aba" -> index 0 ("acca"), index 1 ("bbbb"), index 3 ("acca")
"aba" -> index 0 ("acca"), index 2 ("bbbb"), index 3 ("acca")
"aba" -> index 1 ("caca"), index 2 ("bbbb"), index 3 ("acca")
"aba" -> index 1 ("caca"), index 2 ("bbbb"), index 3 ("caca")

Example 2:

1
2
3
4
5
6
7
8
9


Input:
words = ["abba","baab"], target = "bab"
Output:
 4
Explanation: There are 4 ways to form target.
"bab" -> index 0 ("baab"), index 1 ("baab"), index 2 ("abba")
"bab" -> index 0 ("baab"), index 1 ("baab"), index 3 ("baab")
"bab" -> index 0 ("baab"), index 2 ("baab"), index 3 ("baab")
"bab" -> index 1 ("abba"), index 2 ("baab"), index 3 ("baab")

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.

Solution

Method 1 – Dynamic Programming + Preprocessing

Intuition

Precompute the frequency of each character at each position in words, then use dynamic programming to count the number of ways to form the target string by choosing valid characters from left to right.

Approach

Precompute freq[c][i]: the number of times character c appears at position i in words.
Use dp[i][j]: number of ways to form target[0..i] using columns j and beyond.
For each position in target, try all possible columns and accumulate the ways using the precomputed frequencies.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26


class Solution {
public:
    int numWays(vector<string>& words, string target) {
        int MOD = 1e9+7, m = words[0].size(), n = target.size();
        vector<vector<int>> freq(26, vector<int>(m));
        for (auto& w : words)
            for (int i = 0; i < m; ++i)
                freq[w[i]-'a'][i]++;
        vector<vector<long>> dp(n+1, vector<long>(m+1));
        dp[0][0] = 1;
        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < m; ++j) {
                if (dp[i][j] == 0) continue;
                // skip column j
                dp[i][j+1] = (dp[i][j+1] + dp[i][j]) % MOD;
                // use column j if possible
                int c = target[i]-'a';
                if (freq[c][j] > 0)
                    dp[i+1][j+1] = (dp[i+1][j+1] + dp[i][j] * freq[c][j]) % MOD;
            }
        }
        long res = 0;
        for (int j = 0; j <= m; ++j) res = (res + dp[n][j]) % MOD;
        return res;
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27


func numWays(words []string, target string) int {
    mod := int(1e9+7)
    m, n := len(words[0]), len(target)
    freq := make([][]int, 26)
    for i := range freq { freq[i] = make([]int, m) }
    for _, w := range words {
        for i := 0; i < m; i++ {
            freq[w[i]-'a'][i]++
        }
    }
    dp := make([][]int, n+1)
    for i := range dp { dp[i] = make([]int, m+1) }
    dp[0][0] = 1
    for i := 0; i < n; i++ {
        for j := 0; j < m; j++ {
            if dp[i][j] == 0 { continue }
            dp[i][j+1] = (dp[i][j+1] + dp[i][j]) % mod
            c := target[i]-'a'
            if freq[c][j] > 0 {
                dp[i+1][j+1] = (dp[i+1][j+1] + dp[i][j]*freq[c][j]) % mod
            }
        }
    }
    res := 0
    for j := 0; j <= m; j++ { res = (res + dp[n][j]) % mod }
    return res
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23


class Solution {
    public int numWays(String[] words, String target) {
        int MOD = 1_000_000_007, m = words[0].length(), n = target.length();
        int[][] freq = new int[26][m];
        for (String w : words)
            for (int i = 0; i < m; ++i)
                freq[w.charAt(i)-'a'][i]++;
        long[][] dp = new long[n+1][m+1];
        dp[0][0] = 1;
        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < m; ++j) {
                if (dp[i][j] == 0) continue;
                dp[i][j+1] = (dp[i][j+1] + dp[i][j]) % MOD;
                int c = target.charAt(i)-'a';
                if (freq[c][j] > 0)
                    dp[i+1][j+1] = (dp[i+1][j+1] + dp[i][j] * freq[c][j]) % MOD;
            }
        }
        long res = 0;
        for (int j = 0; j <= m; ++j) res = (res + dp[n][j]) % MOD;
        return (int)res;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25


class Solution {
    fun numWays(words: Array<String>, target: String): Int {
        val MOD = 1_000_000_007
        val m = words[0].length
        val n = target.length
        val freq = Array(26) { IntArray(m) }
        for (w in words)
            for (i in 0 until m)
                freq[w[i]-'a'][i]++
        val dp = Array(n+1) { LongArray(m+1) }
        dp[0][0] = 1L
        for (i in 0 until n) {
            for (j in 0 until m) {
                if (dp[i][j] == 0L) continue
                dp[i][j+1] = (dp[i][j+1] + dp[i][j]) % MOD
                val c = target[i]-'a'
                if (freq[c][j] > 0)
                    dp[i+1][j+1] = (dp[i+1][j+1] + dp[i][j] * freq[c][j]) % MOD
            }
        }
        var res = 0L
        for (j in 0..m) res = (res + dp[n][j]) % MOD
        return res.toInt()
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18


class Solution:
    def numWays(self, words: list[str], target: str) -> int:
        MOD = 10**9+7
        m, n = len(words[0]), len(target)
        freq = [[0]*m for _ in range(26)]
        for w in words:
            for i, c in enumerate(w):
                freq[ord(c)-97][i] += 1
        dp = [[0]*(m+1) for _ in range(n+1)]
        dp[0][0] = 1
        for i in range(n):
            for j in range(m):
                if dp[i][j] == 0: continue
                dp[i][j+1] = (dp[i][j+1] + dp[i][j]) % MOD
                c = ord(target[i])-97
                if freq[c][j] > 0:
                    dp[i+1][j+1] = (dp[i+1][j+1] + dp[i][j]*freq[c][j]) % MOD
        return sum(dp[n][j] for j in range(m+1)) % MOD

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27


impl Solution {
    pub fn num_ways(words: Vec<String>, target: String) -> i32 {
        let m = words[0].len();
        let n = target.len();
        let mut freq = vec![vec![0; m]; 26];
        for w in &words {
            for (i, c) in w.chars().enumerate() {
                freq[c as usize - 'a' as usize][i] += 1;
            }
        }
        let mut dp = vec![vec![0i64; m+1]; n+1];
        dp[0][0] = 1;
        for i in 0..n {
            for j in 0..m {
                if dp[i][j] == 0 { continue; }
                dp[i][j+1] = (dp[i][j+1] + dp[i][j]) % 1_000_000_007;
                let c = target.as_bytes()[i] as usize - 'a' as usize;
                if freq[c][j] > 0 {
                    dp[i+1][j+1] = (dp[i+1][j+1] + dp[i][j] * freq[c][j] as i64) % 1_000_000_007;
                }
            }
        }
        let mut res = 0i64;
        for j in 0..=m { res = (res + dp[n][j]) % 1_000_000_007; }
        res as i32
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24


class Solution {
    numWays(words: string[], target: string): number {
        const MOD = 1e9+7;
        const m = words[0].length, n = target.length;
        const freq: number[][] = Array.from({length: 26}, () => Array(m).fill(0));
        for (const w of words)
            for (let i = 0; i < m; ++i)
                freq[w.charCodeAt(i)-97][i]++;
        const dp: number[][] = Array.from({length: n+1}, () => Array(m+1).fill(0));
        dp[0][0] = 1;
        for (let i = 0; i < n; ++i) {
            for (let j = 0; j < m; ++j) {
                if (dp[i][j] === 0) continue;
                dp[i][j+1] = (dp[i][j+1] + dp[i][j]) % MOD;
                const c = target.charCodeAt(i)-97;
                if (freq[c][j] > 0)
                    dp[i+1][j+1] = (dp[i+1][j+1] + dp[i][j] * freq[c][j]) % MOD;
            }
        }
        let res = 0;
        for (let j = 0; j <= m; ++j) res = (res + dp[n][j]) % MOD;
        return res;
    }
}

Complexity

⏰ Time complexity: O(n * m * 26)
- We precompute frequencies for each character and position, and fill a DP table of size n x m.
🧺 Space complexity: O(n * m + 26 * m)
- The DP table and frequency table are the main space usage.

Number of Ways to Form a Target String Given a Dictionary#

Problem#

Examples#

Solution#

Method 1 – Dynamic Programming + Preprocessing#

Intuition#

Approach#

Code#

Complexity#