题目

题目链接

通过给定词典结构指标字符串的计划数

给你一个字符串列表 words 和一个指标字符串 target 。words 中所有字符串都 长度雷同  。

你的指标是应用给定的 words 字符串列表依照下述规定结构 target ：

  • 从左到右顺次结构 target 的每一个字符。
  • 为了失去 target 第 i 个字符（下标从 0 开始），当 target[i] = words[j][k] 时，你能够应用 words 列表中第 j 个字符串的第 k 个字符。
  • 一旦你应用了 words 中第 j 个字符串的第 k 个字符，你不能再应用 words 字符串列表中任意单词的第 x 个字符（x <= k）。也就是说，所有单词下标小于等于 k 的字符都不能再被应用。
  • 请你反复此过程直到失去指标字符串 target 。

请留神 在结构指标字符串的过程中，你能够依照上述规定应用 words 列表中 同一个字符串 的 多个字符 。

请你返回应用 words 结构 target 的计划数。因为答案可能会很大，请对 109 + 7 取余 后返回。

示例:

输出：words = ["acca","bbbb","caca"], target = "aba"输入：6解释：总共有 6 种办法结构指标串。"aba" -> 下标为 0 ("acca")，下标为 1 ("bbbb")，下标为 3 ("caca")"aba" -> 下标为 0 ("acca")，下标为 2 ("bbbb")，下标为 3 ("caca")"aba" -> 下标为 0 ("acca")，下标为 1 ("bbbb")，下标为 3 ("acca")"aba" -> 下标为 0 ("acca")，下标为 2 ("bbbb")，下标为 3 ("acca")"aba" -> 下标为 1 ("caca")，下标为 2 ("bbbb")，下标为 3 ("acca")"aba" -> 下标为 1 ("caca")，下标为 2 ("bbbb")，下标为 3 ("caca")输出：words = ["abba","baab"], target = "bab"输入：4解释：总共有 4 种不同造成 target 的办法。"bab" -> 下标为 0 ("baab")，下标为 1 ("baab")，下标为 2 ("abba")"bab" -> 下标为 0 ("baab")，下标为 1 ("baab")，下标为 3 ("baab")"bab" -> 下标为 0 ("baab")，下标为 2 ("baab")，下标为 3 ("baab")"bab" -> 下标为 1 ("abba")，下标为 2 ("baab")，下标为 3 ("baab")

提醒:

  • 1 <= words.length <= 1000
  • 1 <= words[i].length <= 1000
  • words 中所有单词长度雷同。
  • 1 <= target.length <= 1000
  • words[i] 和 target 都仅蕴含小写英文字母。

解答

最优的解决方案是应用动静布局 dp ，然而为了更好的了解，首先应用递归进行解答

递归

  • 假如pre是以后的偏移值，idx是target的下标
  • 如果 idx >= len(target) 就阐明是一个解， 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 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)}

动静布局

上述的递归，有很多反复的比拟，如果将target呈现在words的次数保留，那么将缩小次数比拟

  • 假如 cnt(i,j) 是 target[j] 呈现在words的第i列的次数
  • 假如 dp(i,j) 是 target 从0~j时，应用words的0~i列的解答个数
  • dp(i, j) = dp(i-1, j-1) * cnt(i, j) + dp(i-1, j)

实际上，并不需要计算target[j]呈现的次数，而是计算所有26个字母呈现的次数

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)]}