[LeetCode][Python3] 14. Longest Common Prefix

14. Longest Common Prefix

1. 수평 탐색

class Solution:
    def longestCommonPrefix(self, strs: List[str]) -> str:
        if(len(strs)==0): return ""
        prefix = strs[0]
        for i in range(1,len(strs)):
            while(strs[i].find(prefix)!=0):
                prefix = prefix[0:len(prefix)-1]
                if(len(prefix)==0): return ""
        return prefix

 

풀이

접두사 prefix 를 strs[0]으로 설정한 후, strs의 각 요소에게 접근하면서 prefix를 수정한다.

접두사는 단어의 [0:?]에 존재한다는 특징이 있으므로

 prefix=strs[0][0:len(prefix)-1]

을 사용하면 prefix를 찾을 수 있다.

 

복잡도

strs에 한번씩 접근하므로 time complexity(시간 복잡도): O(n) 이다.

prefix를 저장하는 공간만 사용하니 space complexity(공간 복잡도): O(1) 이다.

 

2.수직 탐색

class Solution:
    def longestCommonPrefix(self, strs: List[str]) -> str:
        if(len(strs)==0): return ""
        prePrefix = ""
        prefix = ""
        moreSearch = True
        while(moreSearch):
            for i in range(0,len(strs)):
                if(strs[i].find(prefix)!=0):
                    moreSearch = False
                    break
            if(moreSearch==True):
                prePrefix=prefix
                prefix=strs[0][0:len(prefix)+1]
                if(len(prePrefix)==len(strs[0])): moreSearch = False
        return prePrefix
        

풀이

strs의 각 원소의 0번째 인덱스를 모두 확인한 후, 같다면 다음 인덱스를 체크하는 방법으로 검색한다.

 

복잡도

strs에 strs[0]의 길이만큼 접근하므로 time complexity(시간 복잡도): O(n) 이다.

prefix를 저장하는 공간만 사용하니 space complexity(공간 복잡도): O(1) 이다.

 

리트코드를 참고한 코드

class Solution:
    def longestCommonPrefix(self, strs: List[str]) -> str:
        if(len(strs)==0): return ""
        for i in range(0,len(strs[0])):
            c = strs[0][i]
            for j in range(0,len(strs)):
                if(i == len(strs[j]) or strs[j][i]!=c):
                    return strs[0][0:i]
        return strs[0]