[leetcode-14] Longest Common Prefix

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: 문자열의 개수)