共计 2194 个字符,预计需要花费 6 分钟才能阅读完成。
题目
题目链接
通过给定词典结构指标字符串的计划数
给你一个字符串列表 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)]
}
正文完