23. Longest Common Prefix

문제

배열 strs에 있는 단어들의 가능한 가장 긴 공통 접두어를 찾아라.

Input: strs = ["flower","flow","flight"]
Output: "fl"

 

내가 해결한 방식

strs 배열 정렬 => 0번 인덱스와 끝번 인덱스에 가장 차이가 큰 단어가 위치

0번 인덱스의 단어와 끝번 인덱스 단어의 각 글자를 하나씩 비교해서 일치하면 prefix에 추가.

일치하지 않으면 for문 탈출.

def longestCommonPrefix(self, strs: List[str]) -> str:
    strs.sort()
    prefix = ''

    for i in range(len(strs[0])):
        if strs[0][i] == strs[-1][i]:
            prefix += strs[0][i]
        else:
            break

    return prefix

 

leetcode 유저 해결 방식

https://leetcode.com/problems/longest-common-prefix/discuss/1351149/Python-and-startswith

제일 첫번째 단어를 prefix로 설정.

각 단어를 iterate하면서, 해당 단어가 prefix로 시작할 때까지 prefix를 끝에서부터 한 글자씩 삭제

iterate 후 남은 prefix 반환

def longestCommonPrefix(self, strs: List[str]) -> str:
    prefix = strs[0]

    for str in strs:
        while not str.startswith(prefix):
            prefix = prefix[:-1]

    return prefix