计算一致字符串的数量

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中文网其他相关文章！