辞書が与えられた場合にターゲット文字列を形成する方法の数

1639年。辞書を指定してターゲット文字列を形成する方法の数

難易度: 難しい

トピック: 配列、文字列、動的プログラミング

同じ長さの単語の文字列リストと文字列ターゲットが与えられます。

あなたのタスクは、次のルールの下で指定された単語を使用してターゲットを形成することです:

• ターゲットは左から右に形成する必要があります。
• ターゲットの i ^番目 文字 (0 インデックス付き) を形成するには、j ^{番目 番目 文字を選択できます。 🎜> 単語の文字列 if target[i] = Words[j][k].}
j
• 番目^{の単語文字列の k}番目^{の文字を使用すると、x}番目は使用できなくなります^{。 x}
文字列ターゲットを形成するまでこのプロセスを繰り返します。

上記の条件が満たされている場合、単語内の同じ文字列から複数の文字を使用できることに注意してください。

単語からターゲットを形成する方法の数を返します。答えが大きすぎる可能性があるため、109 ^7.を法にして返します。

例 1:

• 入力: 単語 = ["acca","bbbb","caca"]、ターゲット = "aba"
• 出力: 6
• 説明: ターゲットを形成するには 6 つの方法があります。
  「アバ」 ->インデックス 0 ("acca")、インデックス 1 ("bbbb")、インデックス 3 ("caca")
  「アバ」 ->インデックス 0 ("acca")、インデックス 2 ("bbbb")、インデックス 3 ("caca")
  「アバ」 ->インデックス 0 (「アッカ」)、インデックス 1 (「bbbb」)、インデックス 3 (「アッカ」)
  「アバ」 ->インデックス 0 (「アッカ」)、インデックス 2 (「bbbb」)、インデックス 3 (「アッカ」)
  「アバ」 ->インデックス 1 ("caca")、インデックス 2 ("bbbb")、インデックス 3 ("acca")
  「アバ」 ->インデックス 1 ("caca")、インデックス 2 ("bbbb")、インデックス 3 ("caca")

例 2:

• 入力: 単語 = ["abba","baab"]、ターゲット = "bab"
• 出力: 4
• 説明: ターゲットを形成するには 4 つの方法があります。
  「バブ」 ->インデックス 0 ("baab")、インデックス 1 ("baab")、インデックス 2 ("abba")
  「バブ」 ->インデックス 0 ("baab")、インデックス 1 ("baab")、インデックス 3 ("baab")
  「バブ」 ->インデックス 0 ("baab")、インデックス 2 ("baab")、インデックス 3 ("baab")
  「バブ」 ->インデックス 1 ("abba")、インデックス 2 ("baab")、インデックス 3 ("baab")

制約:

• 1
• 1
• 単語内のすべての文字列は同じ長さです。
• 1
• Words[i] と target には小文字の英字のみが含まれます。

ヒント:

1. 各インデックス i について、各文字の頻度を i ^番目 行に保存します。
2. 動的計画法を使用して、頻度配列を使用してターゲット文字列を取得する方法の数を計算します。

解決策:

この問題では、文字の使用に関する特定のルールに従って、単語の辞書からターゲット文字列を形成する方法を多数見つける必要があります。これは、動的計画法 (DP) と文字頻度の前処理を使用して効率的に解決できる組み合わせ問題です。

重要なポイント

1. 制約:
   • 単語は同じ長さです。
   • 単語内の文字は左から右の方向でのみ使用できます。
2. 課題:
   • 大きな制約があるため、ターゲットを形成する方法を効率的に数えます。
   • メモ化による再計算を回避します。
3. モジュロ:
   • 結果が大きくなる可能性があるため、すべての計算は 10⁹ 7.
   を法として実行されます。

アプローチ

このソリューションでは以下を使用します:

1. 前処理:
   • すべての単語のすべての位置での各文字の頻度を数えます。
2. 動的プログラミング:
   • 2D DP テーブルを使用して、ターゲット文字列を形成する方法の数を計算します。

ステップ:

1. 単語を頻度配列 (カウント) に前処理します。
2. 前処理されたカウントを使用してターゲットを形成する方法の数を再帰的に見つける DP 関数を定義します。

計画

1. 入力解析:
   • 言葉を受け入れて目標を定めます。
2. 前処理:
   • counts[j][char] がすべての単語の位置 j にある char の頻度を表す counts 配列を作成します。
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. 前処理ステップ:

   • カウント配列を構築します。
     • 単語の各列について、各文字の出現数を数えます。
   • 例: 単語 = ["acca", "bbbb", "caca"] の場合、最初の列では counts[0] = {'a': 1, 'b': 1, 'c': 1 }.

2. 再帰 DP:

   • dp(i, j) を定義します。
     • i はターゲットの現在のインデックスです。
     • j はワードでの現在位置です。
   • 基本ケース:
     • If 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 で リポジトリ にスターを付けるか、お気に入りのソーシャル ネットワークで投稿を共有することを検討してください。あなたのサポートは私にとって大きな意味を持ちます!

このような役立つコンテンツがさらに必要な場合は、お気軽にフォローしてください:

• LinkedIn
• GitHub

以上が辞書が与えられた場合にターゲット文字列を形成する方法の数の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。