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: ["flower","flow","flight"]
Output: "fl"


Example 2:


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


Note:

All given inputs are in lowercase letters a-z.

Difficulty: introductory

Starter code:

class Solution:
    def longestCommonPrefix(self, strs: List[str]) -> str:
        

Solutions:
class Solution:
     def longestCommonPrefix(self, strs):
         """
         :type strs: List[str]
         :rtype: str
         """ 
         strs = strs
         import os 
         return os.path.commonprefix(strs)
     
     
 #         for x in strs:
 #            if prefix in x:
 #                 print x
         


class Solution:
     def longestCommonPrefix(self, strs):
         """
         :type strs: List[str]
         :rtype: str
         """
         if not strs:
             return ""
         
         s0 = strs[0]
         shortest_str_len = len(s0)
         
         for s in strs:
             shortest_str_len = min(shortest_str_len, len(s))
 
         for i in range(shortest_str_len):
             for s in strs:
                 if s[i] != s0[i]:
                     if i == 0:
                         return ""
                     else:
                         return s0[0:i]
        
         return s0[0:shortest_str_len]

class Solution:
     def longestCommonPrefix(self, strs):
         """
         :type strs: List[str]
         :rtype: str
         """
         if len(strs) == 0:
             return ""
         
         
         result = ""
         judge = strs[0]
         flag = True
         for i in range(len(judge)):
             for j in strs[1:]:
                 if i >= len(j) or judge[i] != j[i]: 
                     flag = False
             if flag:
                 result += judge[i]
             else:
                 break
             
         return result


class Solution:
     def longestCommonPrefix(self, strs):
         """
         :type strs: List[str]
         :rtype: str
         """
         res = ''
         i = 0
         next_pref = 1
 
         while i < len(strs):
             if strs[i].startswith(res):
                 pass
             else:
                 res = res[:-1]
                 break
             i += 1
             if i == len(strs):
                 if next_pref == -1:
                     break
 
                 res = strs[0][:next_pref]
 
                 i = 0
                 next_pref += 1
                 if next_pref > len(strs[0]):
                     next_pref = -1
         return res

class Solution:
     def longestCommonPrefix(self, strs):
         """
         :type strs: List[str]
         :rtype: str
         """
         def lcp(str1, str2):
             i = 0
             while (i < len(str1)) and (i < len(str2)):
                 print((str1[i], str2[i]))
                 if str1[i] == str2[i]:
                     i += 1
                 else:
                     if i == 0:
                         return ""
                     else:
                         return str1[:i]
             if i == 0:
                 return ""
             else:
                 return str1[:i]
         if not strs:
             return ""
         if len(strs) == 1:
             if not strs[0]:
                 return ""
             else:
                 return strs[0]
         str = lcp(strs[0], strs[1])
         print(str)
         if len(strs) == 2:
             if not str:
                 return ""
             else:
                 return str
         for i in range(1, len(strs)):
             str = lcp(strs[i], str)
         if not str:
             return ""
         else:
             return str 
             
         


class Solution:
     # @return a string
     def longestCommonPrefix(self, strs):
         if not strs:
             return ""
             
         for i, letter_group in enumerate(zip(*strs)):
             if len(set(letter_group)) > 1:
                 return strs[0][:i]
         else:
             return min(strs)


class Solution:
     def longestCommonPrefix(self, strs):
         """
         :type strs: List[str]
         :rtype: str
         """
         if not strs:
             return ""
         shortest = min(strs, key = len)
         for i, val in enumerate(shortest):
             for str in strs:
                 if str[i] != val:
                     return shortest[:i]
         return shortest

class Solution:
     def longestCommonPrefix(self, strs):
         """
         :type strs: List[str]
         :rtype: str
         """
         ############MY SOLUTION############################
         #import numpy as np
         #pref = ""
         #i = 0
         #stop = 0
         
         #if not all(strs): #empty str
         #    return("")
         
         #while not stop:
         #    letter = np.unique([l[i:(i+1)] for l in strs])
         #    if len(letter) == 1 and letter[0] != "" :
         #        pref += letter[0]
         #        i += 1
         #    else:
         #        stop = 1
         #return(pref)
         
         ###########OTHER##################################
         if not strs:   #if strs = []
             return("")
         
         for i, letter_group in enumerate(zip(*strs)):
             if len(set(letter_group)) > 1:
                 return(strs[0][:i])
             
         ##if shortest string is the common prefix or strs contains ""
         else:
             return(min(strs))
                 
 
         


class Solution:
    
     def longestCommonPrefix(self, strs):
         """
         :type strs: List[str]
         :rtype: str
         """
         if not strs:
             return ""
         cpy = strs.copy()
         return self.helper(cpy, 0)
 
     def helper(self, strs, i):
         if i == len(strs) - 1:
             return strs[i]
         s1 = strs[i]
         s2 = strs[i + 1]
         prefix = ""
         if len(s1) == 0 or len(s2) == 0:
             return prefix
         j = 0
         while j < len(s1) and j < len(s2) and s1[j] == s2[j]:
             j += 1
             prefix = s1[:j]
         i += 1
         strs[i] = prefix
         return self.helper(strs, i)


class Solution:
    
     def longestCommonPrefix(self, strs):
         """
         :type strs: List[str]
         :rtype: str
         """
         if not strs:
             return ""
         # 为了不改动原来的数组
         cpy = strs.copy()
         return self.__helper(cpy)  # 记得加 self
 
     '''算出前面两个str的longest common prefix. 然后，把lcp放到第二个str的位置上，strs的第一个元素抛弃，
     递归调用,直到最后只剩一个元素'''
     
     def __helper(self, strs):
         if len(strs) == 1:
             return strs[0]
         s1 = strs[0]
         s2 = strs[1]
         prefix = ""
         if len(s1) == 0 or len(s2) == 0:
             return prefix
         j = 0
         while j < len(s1) and j < len(s2) and s1[j] == s2[j]:
             j += 1
             prefix = s1[:j]
         strs[1] = prefix
         strs.pop(0) # or strs= strs[1:]
         return self.__helper(strs) # 记得加 self


class Solution:
    
     def longestCommonPrefix(self, strs):
         """
         :type strs: List[str]
         :rtype: str
         """
         if not strs:
             return ""
         cpy = strs.copy()
         return self.__helper(cpy)  # 记得加 self
 
     def __helper(self, strs):
         if len(strs) == 1:
             return strs[0]
         s1 = strs[0]
         s2 = strs[1]
         prefix = ""
         if len(s1) == 0 or len(s2) == 0:
             return prefix
         j = 0
         while j < len(s1) and j < len(s2) and s1[j] == s2[j]:
             j += 1
             prefix = s1[:j]
         strs[1] = prefix
         strs = strs[1:]
         return self.__helper(strs) # 记得加 self


class Solution:
     def longestCommonPrefix(self, strs):
         """
         :type strs: List[str]
         :rtype: str
         """
         if not strs or len(strs) == 0:
             return ""
         
         prefix = strs[0]
         
         if len(strs) > 1:
             for i, p in enumerate(prefix):
                 for j in range(1, len(strs)):
                     s = strs[j]
                     if i == len(s) or p != s[i]:
                         return prefix[:i]
                         
                     
                 
                 
             
         
         return prefix
                 
             
                     
         
         
         
             
             


class Solution:
     def _longestCommonPrefix(self, left, right):
         prefix = ''
         i = j = 0
         while(i < len(left) and j < len(right)):
             if left[i] == right[j]:
                 prefix += left[i]
             else:
                 break
             i += 1
             j += 1
         return prefix
     
     def longestCommonPrefix(self, strs):
         """
         :type strs: List[str]
         :rtype: str
         """
         if not strs:
           return ''
         elif len(strs) == 1:
           return strs[0]
         mid = len(strs)//2
         left, right = self.longestCommonPrefix(strs[mid:]), self.longestCommonPrefix(strs[:mid])
         return self._longestCommonPrefix(left, right)


class Solution:
     def longestCommonPrefix(self, strs):
         """
         :type strs: List[str]
         :rtype: str
         """
         if not strs:
             return ''
         for i, letter_group in enumerate(zip(*strs)):
             if len(set(letter_group)) > 1:
                 return strs[0][:i]
         else:
             return min(strs)