[14] Longest Common Prefix | Leetcode Easy

문제설명

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 "".

결과예시

Example 1

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

Example 2

Input: strs = ["dog","racecar","car"]
Output: ""
Explanation: There is no common prefix among the input strings.

제한사항

• 1 <= strs.length <= 200
• 0 <= strs[i].length <= 200
• strs[i] consists of only lower-case English letters.

파이썬 코드

class Solution:
    def longestCommonPrefix(self, strs: List[str]) -> str:
        ret = ""
        if len(str)==0 : return ret
        strs.sort(key = lambda x : len(x))  #문자열 길이가 짧은 순으로 정렬
        minLen = len(strs[0])
        #구하고자하는 longest common prefix의 최대 길이의 한계치는 minLen이 된다.
        for i in range(minLen):
            s = strs[0][i]
            flag = True
            for v in strs:
                if s != v[i] :
                    flag = False
                    break;
            if flag :   #각 자리의 문자가 같다면 ret 뒤에 추가한다.
               ret = ret + s 
            else :
                break   #다르다면 종료
                
        return ret

Time: O(N^2)

다른사람 코드

class Solution:
    def longestCommonPrefix(self, strs):
        prefix=""
        if len(strs)==0: return prefix
        for i in range(len(min(strs,key=len))):
            c=strs[0][i]
            if all(a[i]==c for a in strs):
                prefix+=c
            else:
                break
        return prefix

효율성은 비슷한거 같지만 코드가 더 깔끔하다.

내장함수 any(), all()

• any : 요소중에 하나라도 True가 있으면 True 리턴, 전부다 False이면 False 리턴

• all : 요소 모두가 True이면 True 리턴, 하나라도 False가 있으면 False 리턴

예제

cur = 3
nums = [1,3,10,0]
if any(cur < n for n in nums):
	print("3보다 큰 숫자가 존재합니다.")