文字列内の余分な文字

2707。文字列内の余分な文字

難易度: 中

トピック: 配列、ハッシュ テーブル、文字列、動的プログラミング、トライ

0 インデックス付き 文字列と単語辞書が与えられます。各部分文字列が辞書に存在するように、 を 1 つ以上の 重複しない 部分文字列に分割する必要があります。 s には、どの部分文字列にも存在しない 余分な文字 が含まれている可能性があります。

最適に分割した場合に残る余分な文字の最小数を返します。

例 1:

• 入力: s = "leetcode"、dictionary = ["leet","code","leetcode"]
• 出力: 1
• 説明: s を 2 つの部分文字列に分割できます: インデックス 0 から 3 の「leet」とインデックス 5 から 8 の「code」。未使用の文字は 1 つだけ (インデックス 4) なので、1 を返します。 .

例 2:

• 入力: s = "sayhelloworld"、dictionary = ["hello","world"]
• 出力: 3
• 説明: s を 2 つの部分文字列、つまりインデックス 3 から 7 の「hello」とインデックス 8 から 12 の「world」に分割できます。インデックス 0、1、2 の文字はどの部分文字列でも使用されず、したがって、余分な文字とみなされます。したがって、3 を返します。

制約:

• 1
• 1
• 1
• Dictionary[i] と s は英小文字のみで構成されます
• 辞書には異なる単語が含まれています

ヒント:

1. ここで動的プログラミングを使用できますか?
2. s[0:i] を最適に分割する場合、DP[i] を最小の追加文字として定義します。

解決策:

最適なセグメンテーション後の部分文字列 s[0:i] 内の余分な文字の最小数を dp[i] で表す dp 配列を定義できます。

アプローチ：

1. 動的プログラミングの定義:

   • dp[i] を部分文字列 s[0:i] 内の余分な文字の最小数とします。
   • dp[i] を計算するには、次のことができます。
     • 文字 s[i-1] を余分な文字とみなし、次のインデックスに移動します。
     • または、インデックス i で終わる部分文字列が辞書に存在するかどうかを確認し、存在する場合は、それを使用して余分な文字を減らします。

2. 遷移:

   • 各インデックス i について、次のいずれかを行います。
     • s[i] を追加文字として扱う場合は、dp[i-1] に 1 を追加します。
     • 考えられるすべての部分文字列 s[j:i] (j

3. 結果:

   • dp[len(s)] の値により、文字列 s 全体における余分な文字の最小数が得られます。

このソリューションを PHP で実装してみましょう: 2707。文字列内の余分な文字

<?php /**
 * @param String $s
 * @param String[] $dictionary
 * @return Integer
 */
function minExtraChar($s, $dictionary) {
    ...
    ...
    ...
    /**
     * go to ./solution.php
     */
}

// Test cases
echo minExtraChar("leetscode", ["leet","code","leetcode"]); // Output: 1
echo "\n";
echo minExtraChar("sayhelloworld", ["hello","world"]); // Output: 3
?>

説明：

1. 基本ケース:

   • 空の文字列には余分な文字が存在しないため、dp[0] = 0。

2. 辞書検索:

   • 定数時間検索のために array_flip() を使用して、辞書の単語をハッシュ マップに保存します。

3. 遷移:

   • 各位置 i について、考えられるすべての部分文字列 s[j:i] をチェックします。部分文字列が辞書に存在する場合は、dp[i] 値を更新します。

4. 時間計算量:

   • 時間計算量は O(n^2) です。ここで、n は文字列 s の長さです。これは、インデックスごとに、以前のすべてのインデックスをチェックして部分文字列を形成するためです。

テスト結果:

辞書 ["leet","code","leetcode"] を含む入力 "leetscode" の場合、余分な文字 ("s") が 1 つだけ残っているため、関数は正しく 1 を返します。

辞書 ["hello","world"] を使用した入力 "sayhelloworld" の場合、最初の 3 文字 ("say") が余分であるため、関数は 3 を返します。

連絡先リンク

このシリーズが役立つと思われた場合は、GitHub で リポジトリ にスターを付けるか、お気に入りのソーシャル ネットワークで投稿を共有することを検討してください。あなたのサポートは私にとって大きな意味を持ちます!

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

• LinkedIn
• GitHub

以上が文字列内の余分な文字の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。