給定字典形成目標字串的方法數-php教程-PHP中文網

Number of Ways to Form a Target String Given a Dictionary

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 只包含小寫英文字母。

提示：

對於每個索引 i，儲存第 i^第行中每個字元的頻率。
利用動態規劃，利用頻率陣列計算得到目標字串的方式數。

解：

這個問題需要找到從單字字典中形成目標字串的方法數量，遵循有關字元使用的特定規則。這是一個組合問題，可以使用動態規劃（DP）和預處理字元頻率來有效解決。

要點

限制：
- 單字長度相同。
- 單字中的字元只能以從左到右的方式使用。
挑戰：
- 由於限制條件大，有效計算形成目標的方法。
- 避免透過記憶重新計算。
取模：
- 由於結果可能很大，所有計算均以 10⁹ 7 為模。

接近

解決方案使用：

預處理：
- 計算所有單字中每個位置的每個字元的頻率。
動態規劃：
- 使用二維DP表計算形成目標字串的方式數。

步驟：

將單字預處理為頻率數組（計數）。
定義一個 DP 函數，使用預處理後的計數遞歸地找出形成目標的方法數。

計畫

輸入解析：
- 接受字詞並設定目標。
預處理：
- 建立一個 counts 數組，其中 counts[j][char] 表示所有單字中位置 j 處的 char 出現的頻率。
動態規劃：
- 使用具有記憶功能的遞歸函數來計算使用單字中有效位置的字元形成目標的方法數量。
回傳結果：
- 回傳總計數模 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
?>

登入後複製

解釋：

預處理步驟：
- 建構計數數組：
  - 對於單字中的每一列，計算每個字元的出現次數。
- 範例：如果words = ["acca", "bbbb", "caca"]，對於第一列，counts[0] = {'a': 1, 'b': 1, 'c': 1 }.
遞迴DP:
- 定義 dp(i, j)：
  - i 是目標中的目前索引。
  - j 是單字中的目前位置。
- 基本案例：
  - 如果 i == len(target)：形成整個目標 → 回傳 1。
  - 如果 j == len(words[0])：沒有更多列可供使用 → 傳回 0。
- 復發：
  - 選項 1：使用位置 j 開始的 counts[j][target[i]] 個字元。
  - 選項 2：跳過位置 j。
最佳化：
- 使用記憶表來儲存重疊子問題的結果。

範例演練

輸入:

單字= [“acca”，“bbbb”，“caca”]，目標=“aba”

預處理:
- 計數[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}
DP 計算:
- dp(0, 0): 從第0列開始有多少種方式組成「aba」。
- 結合使用計數和跳列進行遞歸計算。