LeetCode-14
Longest Common Prefix : Write a function to find the longest common prefix string amongst an array of strings.
note : If there is no common prefix, return an empty string "".
Answer
:::python
class Solution:
def longestCommonPrefix(self, strs: List[str]) -> str:
if len(strs)==1:
return strs[0]
answer = ''
i = 0
min_p = min([len(s) for s in strs])
if min_p==0:
return ""
while i < min_p:
if len(set([s[i] for s in strs]))==1:
answer+=strs[0][i]
else:
break
i+=1
return answer
Result : 24ms Memory: 14mb
Longest Common Prefix (최장 공통 접두사)
Longest Common Prefix(최장 공통 접두사)는 문자열 집합에서 공통적으로 나타나는 가장 긴 접두사를 찾는 알고리즘입니다.
예시
예를 들어, 다음과 같은 문자열 집합이 있을 때,
["abcdefg", "abcefg", "abcef"]
공통으로 나타나는 가장 긴 접두사는 "abc"입니다.
알고리즘
Longest Common Prefix를 찾기 위해서는 문자열 집합의 첫 번째 문자열을 기준으로 하여 다른 문자열들과 비교해야 합니다. 각 문자열의 첫 번째 문자부터 차례대로 비교하면서 공통된 부분을 찾습니다.
예시의 문자열 집합에서는 "abcdefg"를 기준으로 하여 다음과 같이 비교합니다.
a b c d e f g
- - - - - - -
a b c e f g
a b c e f
위와 같이 첫 번째 문자열과 다른 문자열을 비교해가면서 모든 문자열에 대해 공통된 접두사를 찾을 때까지 반복합니다.
시간 복잡도
Longest Common Prefix 알고리즘의 시간복잡도는 O(S * N)입니다. (S: 문자열의 평균 길이, N: 문자열의 개수)
'One step' 카테고리의 다른 글
[leetcode-347] Top K Frequent Elements (0) | 2023.04.27 |
---|---|
[leetcode-43] Multiply Strings (0) | 2023.04.26 |
[leetcode-12] Integer to Roman (0) | 2023.04.21 |
[leetcode-10] Regular Expression Matching (0) | 2023.04.20 |
[leetcode-8] String to Integer (atoi) (0) | 2023.04.19 |