Count the Number of Consistent Strings

DDD
Release: 2024-09-13 06:22:02
Original
637 people have browsed it

Count the Number of Consistent Strings

1684. Count the Number of Consistent Strings

Difficulty: Easy

Topics: Array, Hash Table, String, Bit Manipulation, Counting

You are given a string allowed consisting of distinct characters and an array of strings words. A string is consistent if all characters in the string appear in the string allowed.

Return the number of consistent strings in the array words.

Example 1:

  • Input: allowed = "ab", words = ["ad","bd","aaab","baa","badab"]
  • Output: 2
  • Explanation: Strings "aaab" and "baa" are consistent since they only contain characters 'a' and 'b'.

Example 2:

  • Input: allowed = "abc", words = ["a","b","c","ab","ac","bc","abc"]
  • Output: 7
  • Explanation: All strings are consistent.

Example 3:

  • Input: allowed = "cad", words = ["cc","acd","b","ba","bac","bad","ac","d"]
  • Output: 4
  • Explanation: Strings "cc", "acd", "ac", and "d" are consistent.

Constraints:

  • 1 <= words.length <= 104
  • 1 <= allowed.length <= 26
  • 1 <= words[i].length <= 10
  • The characters in allowed are distinct.
  • words[i] and allowed contain only lowercase English letters.

Hint:

  1. A string is incorrect if it contains a character that is not allowed
  2. Constraints are small enough for brute force

Solution:

The idea is to check if each word in the words array is consistent with the characters in the allowed string. A word is consistent if all its characters are present in the allowed string.

Plan

  1. Allowed Characters Set:

    • We can convert the allowed string into a set of characters to efficiently check if each character in the word exists in the set.
  2. Word Consistency Check:

    • For each word in the words array, check if all its characters exist in the allowed set.
  3. Count Consistent Words:

    • Initialize a counter. For each word that is consistent, increment the counter.
  4. Return the Count:

    • Once all words are processed, return the count of consistent words.

Let's implement this solution in PHP: 1684. Count the Number of Consistent Strings

<?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
?>




<h3>
  
  
  Explanation:
</h3>

<ol>
<li>
<p><strong>Allowed Set</strong>:</p>

<ul>
<li>We create an associative array $allowedSet where each key is a character from the allowed string. This allows for fast lookups.</li>
</ul>
</li>
<li>
<p><strong>Word Consistency</strong>:</p>

<ul>
<li>For each word in the words array, we loop through its characters and check if they are in $allowedSet. If we find any character that isn't in the set, the word is marked as inconsistent, and we move on to the next word.</li>
</ul>
</li>
<li>
<p><strong>Counting</strong>:</p>

<ul>
<li>Every time we find a consistent word, we increment the counter $consistentCount.</li>
</ul>
</li>
<li>
<p><strong>Return the Result</strong>:</p>

<ul>
<li>After processing all words, the counter holds the number of consistent strings, which we return.</li>
</ul>
</li>
</ol>

<h3>
  
  
  Time Complexity:
</h3>

<ul>
<li>
<strong>Time Complexity</strong>: O(n * m), where n is the number of words and m is the average length of the words. We are iterating through all the words and their characters.</li>
</ul>

<h3>
  
  
  Example Walkthrough:
</h3>

<p>For the input:<br>
</p>

<pre class="brush:php;toolbar:false">$allowed = "ab";
$words = ["ad", "bd", "aaab", "baa", "badab"];
Copy after login
  • We create a set: allowedSet = ['a' => true, 'b' => true].
  • Checking each word:
    • "ad" is inconsistent (contains 'd').
    • "bd" is inconsistent (contains 'd').
    • "aaab" is consistent (only contains 'a' and 'b').
    • "baa" is consistent (only contains 'a' and 'b').
    • "badab" is inconsistent (contains 'd').

Thus, the function returns 2.

Constraints Handling:

  • Since allowed can only have up to 26 distinct characters, and words has at most 10,000 entries, this brute-force solution is efficient enough given the constraints. Each word can have a maximum length of 10, making it feasible to iterate over all characters.

Contact Links

If you found this series helpful, please consider giving the repository a star on GitHub or sharing the post on your favorite social networks ?. Your support would mean a lot to me!

If you want more helpful content like this, feel free to follow me:

  • LinkedIn
  • GitHub

The above is the detailed content of Count the Number of Consistent Strings. For more information, please follow other related articles on the PHP Chinese website!

source:dev.to
Statement of this Website
The content of this article is voluntarily contributed by netizens, and the copyright belongs to the original author. This site does not assume corresponding legal responsibility. If you find any content suspected of plagiarism or infringement, please contact admin@php.cn
Popular Tutorials
More>
Latest Downloads
More>
Web Effects
Website Source Code
Website Materials
Front End Template