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 reference https leetcode comproblemslongestcommonprefixdescription first solution horizontal scanning second solution vertical scanning third solution divide and conquer first solution horizontal scanning second solution vertical scanning third solution divide and conquer
def common_prefix(s1, s2):
    "Return prefix common of 2 strings"
    if not s1 or not s2:
        return ""
    k = 0
    while s1[k] == s2[k]:
        k = k + 1
        if k >= len(s1) or k >= len(s2):
            return s1[0:k]
    return s1[0:k]

def longest_common_prefix_v1(strs):
    if not strs:
        return ""
    result = strs[0]
    for i in range(len(strs)):
        result = common_prefix(result, strs[i])
    return result


def longest_common_prefix_v2(strs):
    if not strs:
        return ""
    for i in range(len(strs[0])):
        for string in strs[1:]:
            if i == len(string) or string[i] != strs[0][i]:
                return strs[0][0:i]
    return strs[0]


def longest_common_prefix_v3(strs):
    if not strs:
        return ""
    return longest_common(strs, 0, len(strs) -1)

def longest_common(strs, left, right):
    if left == right:
        return strs[left]
    mid = (left + right) // 2
    lcp_left = longest_common(strs, left, mid)
    lcp_right = longest_common(strs, mid + 1, right)
    return common_prefix(lcp_left, lcp_right)