14. Longest Common Prefix - python3

Write a function to find the longest common prefix string amongst an array of strings.

If there is no common prefix, return an empty string "".

My Answer 1: Wrong Answer (111 / 123 test cases passed.)

class Solution:
    def longestCommonPrefix(self, strs: List[str]) -> str:
        if len(strs) < 1:
            return ""
        if len(strs) == 1:
            return strs[0]
        
        minstr = strs[0]
        length = len(strs[0])
        for i in strs:
            if len(i) < length:
                length = len(i)
                minstr = i
                
        prefix = []               # queue
        strprefix = ''.join(prefix) # string
        result = []
        strresult = ''
        
        flag = 0
        
        for i in range(0, length):
            flag = 0
            prefix.append(minstr[i])
            strprefix = ''.join(prefix)
            for j in strs:
                if strprefix not in j:
                    flag = 1
                    break
            if flag == 0:
                result.append(strprefix)
        
        length = 0
        for i in result:
            if length < len(i):
                length = len(i)
                strresult = i
        
        return strresult

첨에 문제 이해를 잘못해서 어떤 위치든 간에 길이가 가장 긴 중복된 문자열을 찾는 건줄 알고 시간을 버렸다.......
(그렇다고 이 코드가 완벽한 것도 아님;)

prefix 의 의미를 제대로 알았어야 했는데...^^

그럼 큐를 사용할 필요가 없으니 쉽게 풀 수 있을듯ㅠㅠ

My Answer 2: Accepted (Runtime: 32 ms - 75.51% / Memory Usage: 14.4 MB - 29.87%)

class Solution:
    def longestCommonPrefix(self, strs: List[str]) -> str:
        if len(strs) < 1:
            return ""
        if len(strs) == 1:
            return strs[0]
        
        minstr = strs[0]
        length = len(strs[0])
        for i in strs:
            if len(i) < length:
                length = len(i)
                minstr = i
        
        prefix = ""
        flag = 0
        
        for i in range(0, length):
            prefix += minstr[i]
            for j in range(0, len(strs)):
                if strs[j][i] != prefix[i]:
                    prefix = prefix[:-1]    # 맨 마지막 삭제
                    flag = 1
                    break
            if flag == 1:
                break
        
        return prefix

1. prefix 에 minstr 을 한글자씩 넣어서 strs 내부의 문자열들과 비교

2. 서로 같은 위치의 문자가 같아야 하므로 둘다 i 위치의 문자가 같은지 비교함

3. 다르면 prefix 의 맨 마지막 부분을 삭제하고 prefix 반환
   (flag 는 이중 for 문이기 때문에 바깥 for 문을 빠져나오기 위한 장치)

• in 은 위치에 상관없이 포함하는지를 판단하기 때문에 적절하지 X

0 <= strs.length <= 200
0 <= strs[i].length <= 200

범위가 작은 편이라 이중 for 문도 성능이 괜찮은듯

스택을 사용해도 될 거 같다
(근데 문자열을 반환해야해서 리스트를 문자열로 형 변환 하는게 좀 복잡할 거 같기도..)