[LeetCode] 14. Longest Common Prefix

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.

 

Constraints:

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

---

이 문제는 공통적으로 갖는 문자열을 구하는 문제이다.

가장 짧은 문장열을 찾은 후 그 문장이 있는지 찾아보며 확인한 후 없다면 한 글자씩 뒤에서 제거하며 반복한다.

 

class Solution:
   def longestCommonPrefix(self, strs):
       short = 99999
       shortStr = ""
       for str in strs:
           if short > len(str):
               short = len(str)
               shortStr = str

       for i in range(0, short):
           now = short-i
           valid = True
           for str in strs:
               if str[:now] != shortStr[:now]:
                   valid = False
                   break
           if valid :
               return shortStr[:now]

       return ""

 

문제 출처 : https://leetcode.com/problems/longest-common-prefix/

Longest Common Prefix - LeetCode

Github : https://github.com/kkkkang1009/leetcode/blob/master/leetcode_14.py

GitHub - kkkkang1009/leetcode: leetcode