[LeetCode] Longest Common Prefix 파이썬 (zip, list comprehension, set)

class Solution:
    def longestCommonPrefix(self, strs: List[str]) -> str:
        strs = [list(x) for x in strs]
        strs = zip(*strs)
        pre = ""
        for a in strs:
            if len(set(a)) == 1:
                pre += a[0]
            else:
                break
        return pre
# output
# [['f', 'l', 'o', 'w', 'e', 'r'], ['f', 'l', 'o', 'w'], ['f', 'l', 'i', 'g', 'h', 't']]
# ('f', 'f', 'f') # a output
# {'f'}           # set(a)
# 1               # len(set(a))
# ('l', 'l', 'l') 
# {'l'}
# 1
# ('o', 'o', 'i')
# {'i', 'o'}
# 2
### OUTPUT ###
fl

기존 리스트에 있는 string element들을 다시 list로 만들어서 word --> character 시킨다. (list comprehension 사용해서 2d list로 변환)

그리고 zip으로 2d리스트에 있는 각 element를 인덱스 기준으로 하나씩 꺼낸다 (for a in strs:)

set 자료형을 사용해서 각 element가 동일한 집합인지 확인한다 (len==1) 동일하면 pre로 만들어놓은 str에 더한다.

집합의 길이가 1개을 초과하면 for 문에서 나온다.

 

list comprehension 에서 list로 했을 때는 28ms, tuple로 했을때는 36ms로 차이가 난다.

메모리는 tuple로 했을때 더 줄었다.

---

class Solution:
    def longestCommonPrefix(self, strs: List[str]) -> str:
        
        strs = zip(*strs)
        pre = ""
        for a in strs:
            if len(set(a)) == 1:
                pre += a[0]
            else:
                break
        return pre

굳이 list comprehension으로 2d 리스트 안만들어도 가능하긴 하다.

근데 2d로 만든게 속도가 더 빠르다.

2d list = 28ms

1d list = 32ms