. 단어 하위 집합

916. 단어 하위 집합

난이도:중

주제: 배열, 해시 테이블, 문자열

두 개의 문자열 배열 word1과 word2가 제공됩니다.

문자열 b는 문자열 a의 하위 집합입니다. 만약 b의 모든 문자가 다중도에 포함되어 있다면

• 예를 들어 "wrr"은 "warrior"의 하위 집합이지만 "world"의 하위 집합은 아닙니다.

words2의 모든 문자열 b에 대해 b가 a의 하위 집합인 경우 word1의 문자열 a는 universal입니다.

words1의 모든 universal 문자열 배열을 반환합니다. 어떤 순서로든 답변을 보내실 수 있습니다.

예 1:

• 입력: word1 = ["amazon","apple","facebook","google","leetcode"], word2 = ["e","o"]
• 출력: ["facebook","google","leetcode"]

예 2:

• 입력: word1 = ["amazon","apple","facebook","google","leetcode"], word2 = ["l","e"]
• 출력: ["apple","google","leetcode"]

제약조건:

• 1 <= 단어1.길이, 단어2.길이 <= 10⁴
• 1 <= 단어1[i].길이, 단어2[i].길이 <= 10
• word1[i]와 word2[i]는 영문 소문자로만 구성됩니다.
• word1의 모든 문자열은 고유합니다.

해결책:

words1에 있는 단어 중 "보편적"인 단어를 식별해야 합니다. 즉, word2의 각 문자열은 word1에 있는 단어의 하위 집합입니다.

접근하다:

1. 단어의 문자 빈도 계산2:

   • 먼저 Words2의 모든 문자열에서 각 문자의 최대 개수를 결정해야 합니다. 이를 통해 각 문자가 하위 집합이 되는 데 필요한 발생 횟수를 알 수 있습니다.

2. 각 단어를 단어로 확인1:

   • words1의 각 단어에 대해 각 문자의 빈도를 계산합니다.
   • 단어 1의 문자 개수가 단어 2의 필수 개수를 충족하거나 초과하면 해당 단어는 보편적입니다.

3. 보편적인 단어 반환:

   • words1의 모든 단어를 확인한 후 보편적인 단어를 반환합니다.

이 솔루션을 PHP로 구현해 보겠습니다: 916. 단어 하위 집합

  
  
  설명:



words2에 대한 빈도 맵 구축: Words2의 각 단어를 반복하고 각 문자의 빈도를 계산합니다. 단어의 모든 단어에 걸쳐 각 문자에 필요한 최대 빈도를 추적합니다2.
단어1 단어 확인: 단어1의 각 단어에 대해 각 문자의 빈도를 계산하고 이를 단어2의 필수 빈도와 비교합니다. 해당 단어가 모든 문자의 요구 사항을 충족하면 보편적인 것으로 간주됩니다.
결과: 모든 범용 단어를 결과 배열에 저장하고 마지막에 반환합니다.



  
  
  시간 복잡도:




단어2에 대한 빈도 맵 구축: O(n * m), 여기서 n은 단어2의 길이이고 m은 단어2의 평균 단어 길이입니다.

단어1 확인: O(k * m), 여기서 k는 단어1의 길이이고 m은 단어1의 평균 단어 길이입니다.
총 시간 복잡도는 대략 O(n * m k * m)입니다.


이러한 접근 방식을 통해 각 단어를 효율적으로 확인하고 문제의 제약 조건을 충족할 수 있습니다.

연락처 링크

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

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


링크드인
깃허브



          

            
  

            
        
위 내용은 . 단어 하위 집합의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!