题目：最长公共前缀

描述 给你一个大小为 n 的字符串数组 strs ，其中包含n个字符串 , 编写一个函数来查找字符串数组中的最长公共前缀，返回这个公共前缀。

数据范围： 0≤n≤5000， 0≤len(strs_i)≤5000 进阶：空间复杂度 O(n)，时间复杂度 O(n)

思路：

解法一：横向比较，先比较前两个字符串的相同部分，存入result，result和下一个比，相同部分作为result，一直到最后一个

解法二：纵向比较,先将第一个字符串的第一个字母拿出来和数组其它字符串第一个比，相同存入result，再取下一个，再比相同再存，不同就返回result

解法三：只需要比较差别最大的两个字符串的前缀即可

# 解法三：
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 
# @param strs string字符串一维数组 
# @return string字符串
#
class Solution:
    def longestCommonPrefix(self , strs: List[str]) -> str:
        # write code here
        if len(strs) == 0:
            return ""
        elif len(strs) == 1:
            return strs[0]
        min_str = strs[0]
        max_str = strs[0]
        for i in strs:
            if i < min_str:
                min_str = i
            if i > max_str:
                max_str = i
        length_str = len(min_str)
        if length_str > len(max_str):
            length_str = len(max_str)
            min_str = min_str[:length_str]
        else :
            max_str = max_str[:length_str]
        if max_str == min_str:
            return min_str
        max_index = length_str
        min_index = 0
        mid_index = 0
        while max_index > min_index:
            mid_index = int((max_index + min_index)>>1)
            result = min_str[:mid_index]
            if max_str.startswith(result):
                min_index = mid_index + 1
            else :
                max_index = mid_index - 1
        result = min_str[:min_index]
        if max_str.startswith(result):
            return result
        else:
            return min_str[:min_index-1]

解法一：用jupyter nootbook写的，大概看一下

strs = ["abca","abc","abca","abc","abcc"]
result = strs[0]
for i in range(1,len(strs),1):
    j = 0
    while j < len(result):
        if (j >= len(strs[i]) or strs[i][j] != result[j]):
            result = result[0:j]
            break
        else:
            j += 1
print(result)

解法二：

strs = ["abca","abc","abca","abc","abcc"]
result = ''
finish = False
for index in range(len(strs[0])):
    i = strs[0][index]
    for j in strs:
        if(len(j)==index):
            finish = True
            break
        if j[index] != i:
            finish = True
            break
    if not finish:
        result += i
    else:
        break
print(result)