LeetCode1639-通过给定词典构造目标字符串的方案数
题目链接
<h3>通过给定词典构造目标字符串的方案数</h3>给你一个字符串列表 words 和一个目标字符串 target 。words 中所有字符串都 长度相同 。
你的目标是使用给定的 words 字符串列表按照下述规则构造 target ：
<ul><li>从左到右依次构造 target 的每一个字符。</li><li>为了得到 <code>target</code> 第 <code>i</code> 个字符（下标从 0 开始），当 <code>target[i] = words[j][k]</code> 时，你可以使用 <code>words</code> 列表中第 <code>j</code> 个字符串的第 <code>k</code> 个字符。</li><li>一旦你使用了 <code>words</code> 中第 <code>j</code> 个字符串的第 <code>k</code> 个字符，你不能再使用 <code>words</code> 字符串列表中任意单词的第 <code>x</code> 个字符（<code>x <= k</code>）。也就是说，所有单词下标小于等于 <code>k</code> 的字符都不能再被使用。</li><li>请你重复此过程直到得到目标字符串 target 。</li></ul>请注意 在构造目标字符串的过程中，你可以按照上述规定使用 words 列表中 同一个字符串 的 多个字符 。
请你返回使用 words 构造 target 的方案数。由于答案可能会很大，请对 109 7 取余 后返回。
示例:
<pre><code class="lang-go hljs">输入：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")</code></code></pre>提示:
<ul><li><code>1 <= words.length <= 1000</code></li><li><code>1 <= words[i].length <= 1000</code></li><li><code>words</code> 中所有单词长度相同。</li><li><code>1 <= target.length <= 1000</code></li><li><code>words[i]</code> 和 <code>target</code> 都仅包含小写英文字母。</li></ul><h2>解答</h2>最优的解决方案是使用动态规划 <code>dp</code> ，但是为了更好的理解，首先使用递归进行解答
递归
<ul><li>假设<code>pre</code>是当前的偏移值，<code>idx</code>是target的下标</li><li>如果 <code>idx >= len(target)</code> 就说明是一个解， return 1</li></ul><pre><code class="lang-go hljs">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) }</code></code></pre>动态规划
上述的递归，有很多重复的比较，如果将target出现在words的次数保存，那么将减少次数比较
<ul><li>假设 <code>cnt(i,j)</code> 是 <code>target[j]</code> 出现在<code>words</code>的第i列的次数</li><li>假设 <code>dp(i,j)</code> 是 <code>target</code> 从0~j时，使用<code>words</code>的0~i列的解答个数</li><li><code>dp(i, j) = dp(i-1, j-1) * cnt(i, j) dp(i-1, j)</code></li></ul>实际上，并不需要计算target[j]出现的次数，而是计算所有26个字母出现的次数
<pre><code class="lang-go hljs">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)] }</code></code></pre>到此这篇关于“LeetCode1639-通过给定词典构造目标字符串的方案数”的文章就介绍到这了,更多文章或继续浏览下面的相关文章，希望大家以后多多支持JQ教程网！
您可能感兴趣的文章：
LeetCode1639-通过给定词典构造目标字符串的方案数
HubbleDotNet 索引分词的测试方法和分词技巧
Python中文分词的原理你知道吗？
如何安装 php scws（分词组件）？
seo搜索引擎关键词技术
Python3爬虫进阶：中文分词（原理、工具）
.net官方编码方法和命名规则
Javascript正则表达式详解（一）
【PHP学习】新手必备PHP常用函数大集合
php中文分词与自动获取关键词的方法