計算一致字串的數量

1684。計算一致字串的數量

難度：簡單

主題：陣列、雜湊表、字串、位元操作、計數

給你一個允許由不同字元和字串單字陣列組成的字串。如果字串中的所有字元都出現在允許的字串中，則字串一致。

傳回陣列單字中一致字串的數量。

範例1：

• 輸入： allowed = "ab", Words = ["ad","bd","aaab","baa","badab"]
• 輸出： 2
• 解釋： 字串「aaab」和「baa」是一致的，因為它們只包含字元「a」和「b」。

範例2：

• 輸入： allowed = "abc", Words = ["a","b","c","ab","ac","bc","abc"]
• 輸出： 7
• 解釋：所有字串都是一致的。

範例 3：

• 輸入： allowed = "cad", Words = ["cc","acd","b","ba","bac","bad","ac","d"]
• 輸出： 4
• 解釋： 字串 "cc"、"acd"、"ac" 和 "d" 是一致的。

約束：

• 1 4
• 1
• 1
• 允許的字元不同。
• Words[i] 和 allowed 只包含小寫英文字母。

提示：

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. 字一致:

   • 對於words數組中的每個單詞，我們循環遍歷它的字元並檢查它們是否在$allowedSet中。如果我們發現任何字元不在集合中，該單字將被標記為不一致，然後我們繼續處理下一個單字。

3. 計數：

   • 每次我們找到一致的單字時，我們都會增加計數器 $concientCount。

4. 回傳結果:

   • 處理完所有單字後，計數器會保存我們傳回的一致字串的數量。

時間複雜度：

• 時間複雜度：O(n * m)，其中n是單字數，m是單字的平均長度。我們正在迭代所有單字及其字符。

演練範例：

輸入：

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

• 我們建立一個集合： allowedSet = ['a' =>;正確，'b' =>是的]。
• 檢查每個單字：
  • “ad”不一致（包含“d”）。
  • “bd”不一致（包含“d”）。
  • 「aaab」是一致的（僅包含'a'和'b'）。
  • 「baa」是一致的（僅包含「a」和「b」）。
  • 「badab」不一致（包含「d」）。

因此，函數傳回 2。

約束處理：

• 由於 allowed 最多只能有 26 個不同的字符，而單字最多有 10,000 個條目，因此在考慮到限制的情況下，這種暴力解決方案足夠有效。每個單字的最大長度為 10，因此可以迭代所有字元。

聯絡連結

如果您發現本系列有幫助，請考慮在 GitHub 上給 存儲庫 一個星號或在您最喜歡的社交網絡上分享該帖子？ 。您的支持對我來說意義重大！

如果您想要更多類似的有用內容，請隨時關注我：

• 領英
• GitHub

以上是計算一致字串的數量的詳細內容。更多資訊請關注PHP中文網其他相關文章！