K 個の回文文字列を構築する

1400。 K 個の回文文字列を構築します

難易度: 中

トピック: ハッシュ テーブル、文字列、貪欲、カウント

文字列 s と整数 k を指定すると、s 内のすべての文字を使用して k 個の回文文字列を構築できる場合は true を返し、それ以外の場合は falseを返します。

例 1:

• 入力: s = "アナベル"、k = 2
• 出力: true
• 説明: s 内のすべての文字を使用して 2 つの回文を作成できます。
  • 考えられる構成例 "anna" "elble"、"anbna" "elle"、"anellena" "b"

例 2:

• 入力: s = "leetcode"、k = 3
• 出力: false
• 説明: s のすべての文字を使用して 3 つの回文を作成することは不可能です。

例 3:

• 入力: s = "true"、k = 4
• 出力: true
• 説明: 唯一可能な解決策は、各文字を別々の文字列に入れることです。

制約:

• 1 5
• s は英小文字で構成されます。
• 1 5

ヒント:

1. s.length
2. 奇数カウントの文字数が > の場合k の場合、構築できる回文文字列の最小数は > です。 k、答えは偽です。
3. それ以外の場合は、正確に k 個の回文文字列を作成でき、答えは true (なぜですか?)。

解決策:

次の点を考慮する必要があります:

主な所見:

1. 回文の特徴:

   • 回文は、前から見ても後ろから見ても同じように読める文字列です。
   • 偶数長の回文の場合、すべての文字が偶数回出現する必要があります。
   • 奇数長の回文の場合、1 文字を除くすべての文字が偶数回出現する必要があります (奇数回出現した文字が中央に表示されます)。

2. 必要な条件:

   • s の長さが k 未満の場合、k 個の文字列を形成することは不可能なので、false を返します。
   • k 個の回文を形成するには、奇数回出現する文字の合計数が最大 k 個でなければなりません。これは、各回文には奇数カウントの文字 (奇数長の回文の中心文字) を最大 1 つ含めることができるためです。

アプローチ：

1. 文字列内の各文字の頻度をカウントします。
2. 奇数の頻度を持つ文字の数を数えます。
3. 奇数の周波数の数が k を超える場合、false を返します (k 個の回文を形成することは不可能であるため)。

このソリューションを PHP で実装してみましょう: 1400。 K 個の回文文字列を構築します

<?php
/**
 * @param String $s
 * @param Integer $k
 * @return Boolean
 */
function canConstruct($s, $k) {
    ...
    ...
    ...
    /**
     * go to ./solution.php
     */
}

// Test cases
var_dump(canConstruct("annabelle", 2)); // Output: true
var_dump(canConstruct("leetcode", 3)); // Output: false
var_dump(canConstruct("true", 4));      // Output: true
?>

説明：

1. 頻度カウント: 連想配列 $freq を使用して、文字列内の各文字の出現をカウントします。
2. 奇数カウント: 奇数の出現がある文字の数をチェックします。これは、回文を形成できるかどうかを判断するのに役立ちます。
3. 条件チェック: 奇数の頻度を持つ文字の数が k より大きい場合、k 個の回文を形成することは不可能であるため、false を返します。それ以外の場合は true を返します。

時間計算量:

• 頻度のカウントには O(n) がかかります。n は文字列の長さです。
• 奇数の頻度のチェックには O(m) がかかります。ここで、m は個別の文字の数です (英小文字の場合は最大 26)。
• 全体的な時間計算量は O(n m) で、この場合は O(n) に単純化されます。

エッジケース:

1. k が s の長さより大きい場合、false を返します。
2. すべての文字の頻度が偶数であれば、いつでも回文を形成できるため、結果は k が可能かどうかによって決まります。

連絡先リンク

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

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

• LinkedIn
• GitHub

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