Leetcode 2185. Counting Words With a Given Prefix

2024년 1월 9일 (목)
Leetcode daily problem

2185. Counting Words With a Given Prefix

https://leetcode.com/problems/counting-words-with-a-given-prefix/description/?envType=daily-question&envId=2025-01-09

문자열 배열 words와 pref 문자열이 주어질 때, words 배열 내의 문자열이 pref로 시작하는(접두사인) 갯수를 반환한다.

Solution

startswith 함수 사용하기

각 배열을 순환하면서 pref와 startswith 함수로 비교해서 카운트한다.

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

시간 복잡도

전체 주어진 배열의 words의 길이만큼 순환하므로 길이를 n이라고 할 때 선형적으로 O(n)이 소요되고, 각 문자열을 배열을 비교 할 때는 pref의 길이를 k라고 할 때 startswith 는 O(k) 만큼의 시간이 소요되므로
전체 시간복잡도는 O(n*k)이다.

공간 복잡도

정수 변수 ans만 사용하기 때문에 공간복잡도는 O(1) 이다.