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 <= 10⁴
• 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"];

• 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.

제약 조건 처리:

• 허용되는 문자는 최대 26개이고 단어에는 최대 10,000개의 항목이 있으므로 이 무차별 대입 솔루션은 제약 조건을 고려할 때 충분히 효율적입니다. 각 단어의 최대 길이는 10이므로 모든 문자에 대해 반복이 가능합니다.

연락처 링크

이 시리즈가 도움이 되었다면 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!