[LeetCode OJ] Longest Common Prefix - Easy Algorithm

<Problem Link>



<Comment>

우어.. 정말 오랜만에 알고리즘 포스팅... ㅋㅋ
요샌 일이 바쁘다 보니 알고리즘 문제풀 시간도 별로 없는것 같다.
어쨋든 이 문제 역시 큰 어려움 없이 매우 단순한 방법으로 해결 하였다.
사실 이것 문제를 해결하는데에는 다양한 방법이 있다.

- 들어온 문자열을 순서대로 앞의 문자열부터 비교하여 LongestPrefix를 갱신해 가며 마지막까지 스캔 한뒤 리턴 (현재Solution)
- 입력 리스트를 문자열에 대해 사전처럼 Sort한뒤 첫번째와 마지막 문자열의 공통 Prefix 리턴 (중간 단어들은 모두 공통된 Prefix를 가지고 있음을 이용)
- 리스트 내 모든 문자열에 대해 문자 자릿수 하나하나를 점검 해 나가며 공통 prefix를 생성해 가는 방식.


<Solution> Python - Accepted

================================================
실행시간 : 57ms
시간복잡도 : O(NL) - N:문자열 개수, L:문자열 평균길이
공간복잡도 : O(1)
================================================

class Solution:
    def getPrefix(self, a, b) :
        l = len(a)
        if len(b) < l :
            l = len(b)
        prefix = ""
        for i in range(0,l) :
            if a[i] == b[i] :
                prefix += a[i]
            else :
                break
        return prefix
            
    # @return a string
    def longestCommonPrefix(self, strs):

// 예외처리 먼저
        if len(strs) == 0 :
            return ""
        if len(strs) == 1 :
            return strs[0]
        longestPrefix = self.getPrefix(strs[0], strs[1])
        if len(strs) == 2 :
            return longestPrefix

// 최장 Prefix를 갱신해가며 루프돌기
        for i in range(2, len(strs)) :
            s = strs[i]
            if s.startswith(longestPrefix) :
                continue
            else :
                longestPrefix = self.getPrefix(longestPrefix, s)
            if longestPrefix == "" :
                break
        return longestPrefix




통계 위젯 (블랙)

8221
1191
243251

GoogleAdsenseResponsive

Cluster map