2024년 1월 8일 (수)
Leetcode daily problem
leetcode 3042. Count Prefix and Suffix Pairs I
문자열로 구성된 words 배열이 주어질 때,다음 조건을 만족하는 (i,j)의 쌍의 개수를 구하는 것이다.
조건은 i<j 이고 isPrefixAndSuffix(words[i], words[j])가 true인 경우이다.
isPrefixAndSuffix(str1, str2)는 str1이 str2의 접두사이자 접미사인지를 검사하는 함수이다.
예를 들어, isPrefixAndSuffix("aba", "ababa")는 true를 반환한다. 왜냐하면 "aba"는 "ababa"의 접두사이자 접미사이기 때문이다.
반면에 isPrefixAndSuffix("abc", "abcd")는 false를 반환한다. 왜냐하면 "abc"는 "abcd"의 접두사는 맞지만 접미사는 아니기 때문이다.
Solution
두 문자열을 슬라이싱하거나 함수를 사용해서 비교하기
각 문자열의 배열을 앞에서 뒤로 순환하면서 슬라이싱해서 비교한다.
혹은 startwith, endswith 함수를 사용해서 비교한다.
Code
방법 1. 처음에 풀었을 때
class Solution:
def countPrefixSuffixPairs(self, words: List[str]) -> int:
ans = 0
for i in range(len(words)):
for j in range(i+1, len(words)):
word_len = len(words[i])
if words[i] == words[j][:word_len] and words[i] == words[j][-word_len:]:
ans+=1
return ans방법 2 함수 사용
startswith, endswith 함수 사용한다.
class Solution:
def countPrefixSuffixPairs(self, words: List[str]) -> int:
ans = 0
for i in range(len(words)):
for j in range(i+1, len(words)):
if words[j].startswith(words[i]) and words[j].endswith(words[i]):
ans+=1
return ans
Complexicity
시간 복잡도
첫 번째 방법은 이중 for 루프를 사용하는데 첫번째 i 루프와 두번째 j 루프는 len(words) 만큼 반복되므로 O(n^2) 이다.
그리고 문자열을 비교하는 부분에서 최악의 경우 문자열의 길이 만큼 반복해서 문자열 word[i]의 길이를 k 라고 했을 때 O(k) 가 된다.
즉 전체 시간 복잡도는 O(n^2 *k) 가된다. n은 words 배열의 개수, k는 각 문자열의 평균 길이이다.
두 번째 방법은 이중 루프를 돌기 때문에 words의 배열의 길이만큼인 O(n^2) 이 걸리고, 각 접두사와 접미사를 체크하는 words[i], words[j]의 문자열의 최대 길이인 O(m)의 시간이 걸린다. 그래서 전체 시간 복잡도는 O(n^2*m) 이다.
공간 복잡도
첫 번째 방법은 ans에서 하나의 정수 값을 저장해 O(1)이다.
두 번째 방법은 ans 하나의 정수를 저장해 O(1) 이다.
첫 번째
두 번째
