일관된 문자열 수 계산

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 <= 허용.길이 <= 26
• 1 <= 단어[i].length <= 10
• 허용되는 문자는 뚜렷한 문자입니다.
• 단어[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
?>




<h3>
  
  
  설명:
</h3>

<ol>
<li>
<p><strong>허용된 세트</strong>:</p>

<ul>
<li>각 키가 허용된 문자열의 문자인 $allowedSet 연관 배열을 생성합니다. 이를 통해 빠른 조회가 가능합니다.</li>
</ul>
</li>
<li>
<p><strong>단어 일관성</strong>:</p>

<ul>
<li>단어 배열의 각 단어에 대해 해당 문자를 반복하여 $allowedSet에 있는지 확인합니다. 세트에 없는 문자를 찾으면 해당 단어는 불일치로 표시되고 다음 단어로 넘어갑니다.</li>
</ul>
</li>
<li>
<p><strong>계산</strong>:</p>

<ul>
<li>일관적인 단어를 찾을 때마다 $consistantCount 카운터가 증가합니다.</li>
</ul>
</li>
<li>
<p><strong>결과 반환</strong>:</p>

<ul>
<li>모든 단어를 처리한 후 카운터는 일관된 문자열 수를 보유하고 이를 반환합니다.</li>
</ul>
</li>
</ol>

<h3>
  
  
  시간 복잡도:
</h3>

<ul>
<li>
<strong>시간 복잡도</strong>: O(n * m), 여기서 n은 단어 수이고 m은 단어의 평균 길이입니다. 모든 단어와 해당 문자를 반복하고 있습니다.</li>
</ul>

<h3>
  
  
  예제 연습:
</h3>

<p>입력:<br>
</p>

<pre class="brush:php;toolbar:false">$allowed = "ab";
$words = ["ad", "bd", "aaab", "baa", "badab"];

• 세트를 만듭니다: allowedSet = ['a' => 사실, 'b' => 사실].
• 각 단어 확인하기:
  • 'ad'가 일치하지 않습니다('d' 포함).
  • 'bd'는 일관성이 없습니다('d' 포함).
  • "aaab"은 일관성이 있습니다('a'와 'b'만 포함).
  • "baa"는 일관성이 있습니다('a'와 'b'만 포함).
  • "badab"은 일관성이 없습니다('d' 포함).

따라서 함수는 2를 반환합니다.

제약 조건 처리:

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

연락처 링크

이 시리즈가 도움이 되었다면 GitHub에서 저장소에 별표를 표시하거나 즐겨찾는 소셜 네트워크에서 게시물을 공유해 보세요. 여러분의 지원은 저에게 큰 의미가 될 것입니다!

이렇게 더 유용한 콘텐츠를 원하시면 저를 팔로우해주세요.

• 링크드인
• 깃허브

위 내용은 일관된 문자열 수 계산의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!