一貫した文字列の数を数える

1684年。一貫した文字列の数を数える

難易度: 簡単

トピック: 配列、ハッシュ テーブル、文字列、ビット操作、カウント

個別の文字と文字列単語の配列で構成される許可された文字列が与えられます。文字列内のすべての文字が許可された文字列に含まれる場合、文字列は 一貫性 です。

配列ワード内の一貫した文字列の数を返します。

例 1:

• 入力: 許可 = "ab"、単語 = ["ad","bd","aaab","baa","badab"]
• 出力: 2
• 説明: 文字列「aaab」と「baa」には文字「a」と「b」のみが含まれるため、一貫性があります。

例 2:

• 入力: 許可 = "abc"、単語 = ["a","b","c","ab","ac","bc","abc"]
• 出力: 7
• 説明: すべての文字列は一貫しています。

例 3:

• 入力: 許可 = "cad"、単語 = ["cc","acd","b","ba","bac","bad","ac","d"]
• 出力: 4
• 説明: 文字列「cc」、「acd」、「ac」、および「d」は一貫しています。

制約:

• 1 4
• 1
• 1
• 許可されている文字は 異なるです。
• 単語[i] および許可されるのは、小文字の英文字のみです。

ヒント:

1. 許可されていない文字が含まれている場合、文字列は正しくありません
2. 制約はブルートフォースに十分小さい

解決策:

その目的は、単語配列内の各単語が、許可された文字列内の文字と一貫性があるかどうかをチェックすることです。すべての文字が許可された文字列内に存在する場合、単語は一貫性となります。

プラン

1. 使用できる文字セット:

   • 許可された文字列を文字セットに変換して、単語内の各文字がセット内に存在するかどうかを効率的にチェックできます。

2. 単語の一貫性チェック:

   • 単語配列内の各単語について、そのすべての文字が許可されたセットに存在するかどうかを確認します。

3. 一貫した単語を数える:

   • カウンターを初期化します。一致する単語ごとに、カウンターをインクリメントします。

4. カウントを返す:

   • すべての単語が処理されたら、一致する単語の数を返します。

このソリューションを PHP で実装してみましょう: 1684。一致する文字列の数を数える

<?php
/**
 * @param String $allowed
 * @param String[] $words
 * @return Integer
 */
function countConsistentStrings($allowed, $words) {
    ...
    ...
    ...
    /**
     * go to ./solution.php
     */
}

// Example usage:

// Example 1:
$allowed = "ab";
$words = ["ad", "bd", "aaab", "baa", "badab"];
echo countConsistentStrings($allowed, $words); // Output: 2

// Example 2:
$allowed = "abc";
$words = ["a","b","c","ab","ac","bc","abc"];
echo countConsistentStrings($allowed, $words); // Output: 7

// Example 3:
$allowed = "cad";
$words =  ["cc","acd","b","ba","bac","bad","ac","d"];
echo countConsistentStrings($allowed, $words); // Output: 4
?>

説明：

1. 許可されたセット:

   • 各キーが許可された文字列の文字である連想配列 $allowedSet を作成します。これにより、高速な検索が可能になります。

2. 単語の一貫性:

   • 単語配列内の単語ごとに、その文字をループし、それらが $allowedSet 内にあるかどうかを確認します。セットに含まれていない文字が見つかった場合、その単語は矛盾しているとマークされ、次の単語に進みます。

3. カウント中:

   • 一貫した単語が見つかるたびに、カウンター $consistentCount をインクリメントします。

4. 結果を返す:

   • すべての単語を処理した後、カウンターには一貫した文字列の数が保持され、それが返されます。

時間計算量:

• 時間計算量: O(n * m)、n はワード数、m はワードの平均長です。すべての単語とその文字を繰り返し処理します。

チュートリアルの例:

入力用:

$allowed = "ab";
$words = ["ad", "bd", "aaab", "baa", "badab"];

• セットを作成します: allowedSet = ['a' => true、'b' => true].
• 各単語を確認する:
  • 「ad」に一貫性がありません (「d」が含まれています)。
  • 「bd」は矛盾しています (「d」が含まれています)。
  • 「aaab」は一貫しています (「a」と「b」のみが含まれます)。
  • 「baa」は一貫しています (「a」と「b」のみが含まれます)。
  • 「badab」は一貫性がありません (「d」が含まれています)。

したがって、この関数は 2 を返します。

制約の処理:

• 許可されるのは最大 26 個の異なる文字のみであり、単語には最大 10,000 個のエントリがあるため、制約を考慮すると、この総当たりソリューションは十分に効率的です。各単語の最大長は 10 であるため、すべての文字を反復処理できます。

連絡先リンク

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

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

• LinkedIn
• GitHub

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