leetcode 916. Word Subsets

2024년 1월 10일 (금)
Leetcode daily problem

916. Word Subsets

https://leetcode.com/problems/word-subsets/description/?envType=daily-question&envId=2025-01-10

문자열 b가 문자열 a이 subset이 되려면 b의 모든 문자가 a에 포함되어야 하고, 각 문자의 빈도도 a에서 최소한 b의 빈도만큼 있어야 한다.

문자열 배열 words1, words2가 주어질 때 words2의 모든 문자열이 words1의 배열에 있는 문자열의 subset 이라면 해당 문자열을 반환한다.

Solution

문자열 빈도

word2에 있는 문자열의 빈도와 words1에 문자열이 조건을 만족하는지 확인한다.

Code

class Solution:
    def prefixCount(self, words: List[str], pref: str) -> int:
        ans = 0
        for i in range(len(words)):
            if words[i].startswith(pref):
                ans +=1

        return ans

Complexicity

시간 복잡도

words2의 최대 빈도를 계산할 때 각 문자열에 대해서 문자열 길이를 n이라고 하면 O(n)이 소요되고, 최대 빈도를 계산하는 반복문인 고정길이 O(26)은 O(1)이다.
words2에 있는 모든 문자열의 총합을 L2라고 하면 O(L2)가 소요된다.

words1에서도 문자열의 길이를 m이라고 하면 O(m), 조건을 반복하는 O(26) = O(1). words1에 있는 모든 문자열의 길이의 총합을 L1라고 한다면 O(L1)으로

전체 시작 복잡도는 O(L2) + O(L1) = O(L1+L2) 이다.

공간 복잡도

정수 변수 ans만 사용하기 때문에 공간복잡도는 O(1) 이고,,
결과 리스트 ans에서 word1 만큼 최대로 들어갈 수 있어서 word1의 길이가 k라고 한다면 공간복잡도는 O(k) 이다.
출력 길이를 무시하면 O(1) 이라고 볼 수 있다.