The title

The number of scenarios for constructing the target string from a given dictionary

It gives you a list of strings, words and a target string. All strings in words are of the same length.

Your goal is to construct a target using a given list of words strings according to the following rules:

• Construct each character of target from left to right.
• In order to get`target` 第 `i`Character (subscript starts at 0), when`target[i] = words[j][k]`“, you can use`words`The list of the first`j`The first of a string`k`A character.
• Once you use it`words`In the first`j`The first of a string`k`A character you can no longer use`words`The first word in a string list`x`A character (`x <= k`). In other words, all words have subscripts less than or equal to`k`Can no longer be used.
• Repeat this process until you get the target string.

Note that when constructing the target string, you can use more than one character of the same string in the words list as described above.

Please return the number of scenarios in which words were used to construct the target. Since the answer is likely to be large, rest 109 + 7 and return.

Example:

``Input: words = ["acca"," BBBB ","caca"], target = "aba" output: 6 Explanation: There are 6 ways to construct the target string. "Aba" - > subscript to 0 (acca), the subscript 1 (" BBBB "), the subscript 3 (" caca ") "aba" - > subscript to 0 (acca), the subscript 2 (" BBBB "), Subscript 3 ("caca"), "aba" -> subscript 0 ("acca"), subscript 1 (" BBBB "), subscript 3 ("acca"), "aba" -> subscript 0 ("acca"), subscript 2 (" BBBB "), Subscript 3 (" ACCA "), "ABA" -> subscript 1 ("caca"), subscript 2 (" BBBB "), subscript 3 ("acca"), "ABA" -> subscript 1 ("caca"), subscript 2 (" BBBB "), Subscript 3 ("caca") input: words = ["abba","baab"], target = "bab" output: 4 Explanation: There are 4 different ways to form a target. "Bab" - > subscript of 0 (" baab "), the subscript 1 (" baab "), the subscript 2 (" abba "), "the bab" - > subscript of 0 (" baab "), the subscript 1 (" baab "), Subscript 3 ("baab") "bab" -> subscript 0 ("baab"), subscript 2 ("baab"), subscript 3 ("baab") "bab" -> subscript 1 ("abba"), subscript 2 ("baab"), The subscript is 3 ("baab").``

Tip:

• `1 <= words.length <= 1000`
• `1 <= words[i].length <= 1000`
• `words`All words are of the same length.
• `1 <= target.length <= 1000`
• `words[i]``target`Contains only lowercase English letters.

The optimal solution is to use dynamic programming DP, but for better understanding, first use recursion for the solution

recursive

• Assuming that`pre`Is the current offset value,`idx`Is the subscript of target
• if`idx >= len(target)`That means phi is a solution, return 1
``func helper(words []string, idx int, target string, pre int) int{ const MOD = 1e9 + 7 if idx >= len(target) { return 1 } sum := 0 for _, word := range words { for s := pre; s < len(word); S++ {// If the current character matches the target character, If c == target[idx] {sum += helper(words, idx + 1, target, s + 1) } } } return sum % MOD } func numWays(words []string, target string) int { return helper(words, 0, target 0) }``

Dynamic programming

In the above recursion, there are many repeated comparisons. If we save the number of occurrences of target in words, the number of comparisons will be reduced

• Assuming that`cnt(i,j)``target[j]`Appear in the`words`The degree of column I of
• Assuming that`dp(i,j)``target`From 0 to j, using`words`The number of solutions to columns 0~ I of
• `dp(i, j) = dp(i-1, j-1) * cnt(i, j) + dp(i-1, j)`

Instead of counting the number of occurrences of target[j], you actually count the number of occurrences of all 26 letters

``````func numWays(words []string, target string) int {
const MOD = 1e9 + 7
cnts := make([][]int, len(words[0]))
for i := range cnts {
cnts[i] = make([]int, 26)
}
for _, word := range words {
for i, char := range word {
cnts[i][char-'a']++
}
}
dp := make([][]int, len(words[0])+1)
for i := range dp {
dp[i] = make([]int, len(target)+1)
dp[i][0] = 1
}
for i := 1; i <= len(words[0]); i++ {
for j := 1; j <= len(target); j++ {
dp[i][j] = (dp[i-1][j-1]*cnts[i-1][target[j-1]-'a'] + dp[i-1][j]) % int(MOD)
}
}
return dp[len(words[0])][len(target)]
}``````