给定字典形成目标字符串的方法数

1639。给定字典形成目标字符串的方法数

难度：难

主题：数组、字符串、动态编程

您将获得一个相同长度个单词的字符串列表和一个字符串目标。

您的任务是根据以下规则使用给定的单词形成目标：

• 目标应从左到右形成。
• 要形成目标的第 i 个字符（0-索引），您可以选择第 j^{第 k}第 ^个字符 单词中的字符串，如果 target[i] = Words[j][k].
• 一旦您使用了第 j^第 个单词字符串中的第 k^第 个字符，您就不能再使用第 x^第 单词中任何字符串的字符，其中 x
• 重复该过程，直到形成字符串目标。

注意，只要满足上述条件，您可以在单词中使用同一字符串中的多个字符。

返回从单词形成目标的方式数。由于答案可能太大，请返回模 10⁹ 7.

示例1：

• 输入： 单词 = ["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”）

示例2：

• 输入： 单词 = ["abba","baab"], 目标 = "bab"
• 输出： 4
• 说明：有 4 种方式形成目标。
  • “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
• 1
• 单词中的所有字符串都具有相同的长度。
• 1
• words[i] 和 target 只包含小写英文字母。

提示：

1. 对于每个索引 i，存储第 i^第 行中每个字符的频率。
2. 利用动态规划，利用频率数组计算得到目标字符串的方式数。

解决方案：

这个问题需要找到从单词字典中形成目标字符串的方法数量，遵循有关字符使用的特定规则。这是一个组合问题，可以使用动态规划（DP）和预处理字符频率来有效解决。

要点

1. 限制：
   • 单词长度相同。
   • 单词中的字符只能以从左到右的方式使用。
2. 挑战：
   • 由于约束条件大，有效计算形成目标的方法。
   • 避免通过记忆重新计算。
3. 取模：
   • 由于结果可能很大，所有计算均以 10⁹ 7 为模。

接近

解决方案使用：

1. 预处理：
   • 计算所有单词中每个位置的每个字符的频率。
2. 动态规划：
   • 使用二维DP表计算形成目标字符串的方式数。

步骤：

1. 将单词预处理为频率数组（计数）。
2. 定义一个 DP 函数，使用预处理后的计数递归地查找形成目标的方法数。

计划

1. 输入解析：
   • 接受词语并设定目标。
2. 预处理：
   • 创建一个 counts 数组，其中 counts[j][char] 表示所有单词中位置 j 处的 char 出现的频率。
3. 动态规划：
   • 使用具有记忆功能的递归函数来计算使用单词中有效位置的字符形成目标的方法数量。
4. 返回结果：
   • 返回总计数模 10⁹ 7.

让我们用 PHP 实现这个解决方案：1639。给定字典形成目标字符串的方法数

<?php const MOD = 1000000007;
/**
 * @param String[] $words
 * @param String $target
 * @return Integer
 */
function numWays($words, $target) {
    ...
    ...
    ...
    /**
     * go to ./solution.php
     */
}

/**
 * Helper function for DP
 *
 * @param $i
 * @param $j
 * @param $counts
 * @param $target
 * @param $memo
 * @return float|int|mixed
 */
private function dp($i, $j, $counts, $target, &$memo) {
    ...
    ...
    ...
    /**
     * go to ./solution.php
     */
}

// Example Usage
$words = ["acca", "bbbb", "caca"];
$target = "aba";
echo numWays($words, $target) . "\n"; // Output: 6

$words = ["abba", "baab"];
$target = "bab";
echo numWays($words, $target) . "\n"; // Output: 4
?>

解释：

1. 预处理步骤：

   • 构建计数数组：
     • 对于单词中的每一列，计算每个字符的出现次数。
   • 示例：如果words = ["acca", "bbbb", "caca"]，对于第一列，counts[0] = {'a': 1, 'b': 1, 'c': 1 }.

2. 递归DP:

   • 定义 dp(i, j)：
     • i 是目标中的当前索引。
     • j 是单词中的当前位置。
   • 基本案例：
     • 如果 i == len(target)：形成整个目标 → 返回 1。
     • 如果 j == len(words[0])：没有更多列可供使用 → 返回 0。
   • 复发：
     • 选项 1：使用位置 j 开始的 counts[j][target[i]] 个字符。
     • 选项 2：跳过位置 j。

3. 优化：

   • 使用记忆表来存储重叠子问题的结果。

示例演练

输入:

单词= [“acca”，“bbbb”，“caca”]，目标=“aba”

1. 预处理:

   • 计数[0] = {'a': 2, 'b': 0, 'c': 1}
   • 计数[1] = {'a': 0, 'b': 3, 'c': 0}
   • 计数[2] = {'a': 1, 'b': 0, 'c': 2}
   • 计数[3] = {'a': 2, 'b': 0, 'c': 1}

2. DP 计算:

   • dp(0, 0): 从第0列开始有多少种方式组成“aba”。
   • 结合使用计数和跳列进行递归计算。

输出：6

时间复杂度

1. 预处理：O(n x m)，其中n是单词数量，m是单词长度。
2. 动态规划：O(l x m)，其中l是目标的长度。
3. 总计：O(n x m l x m)。

示例输出

• 输入： 单词= [“acca”，“bbbb”，“caca”]，目标=“aba”
• 输出：6

这个问题是结合预处理和动态规划来有效解决组合挑战的一个很好的例子。

联系链接

如果您发现本系列有帮助，请考虑在 GitHub 上给 存储库 一个星号或在您最喜欢的社交网络上分享该帖子？。您的支持对我来说意义重大！

如果您想要更多类似的有用内容，请随时关注我：

• 领英
• GitHub

以上是给定字典形成目标字符串的方法数的详细内容。更多信息请关注PHP中文网其他相关文章！