The title

Topic link

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 gettarget 第 iCharacter (subscript starts at 0), whentarget[i] = words[j][k]“, you can usewordsThe list of the firstjThe first of a stringkA character.
  • Once you use itwordsIn the firstjThe first of a stringkA character you can no longer usewordsThe first word in a string listxA character (x <= k). In other words, all words have subscripts less than or equal tokCan 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
  • wordsAll words are of the same length.
  • 1 <= target.length <= 1000
  • words[i] 和 targetContains only lowercase English letters.

answer

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

recursive

  • Assuming thatpreIs the current offset value,idxIs the subscript of target
  • ifidx >= 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 thatcnt(i,j) 是 target[j]Appear in thewordsThe degree of column I of
  • Assuming thatdp(i,j) 是 targetFrom 0 to j, usingwordsThe 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)]
}