首页 > 试题广场 >

最长公共前缀

[编程题]最长公共前缀

热度指数：173053 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

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

数据范围： $0 \le n \le 5000$ ， $0 \le len(strs_i) \le 5000$

进阶：空间复杂度 $O(1)$ ，时间复杂度 $O(n*len)$

示例1

输入

["abca","abc","abca","abc","abcc"]

输出

"abc"

示例2

输入

["abc"]

输出

"abc"

算法知识视频讲解

查看答案及解析

Python3

牛客408727824号

class Solution:

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

# write code here

if len(strs) == 0 or len(strs[0]) == 0:

return ""

for i in range(len(strs[0])):

for j in range(1,len(strs)):

if i>len(strs[j])-1:

return strs[0][:i]

if strs[j][i] != strs[0][i]:

return strs[0][:i]

return strs[0]

发表于 2025-10-17 00:57:46 回复(0)

Python3

要冲外企的干饭人很喜欢拱白菜

先处理特殊情况：如果strs为空，直接返回空字符串""。

最长公共前缀长度不会超过数组中最短字符串的长度，所以先找出长度最短的字符串min_str。

逐字符比较min_str的每个位置i：检查数组中每个字符串在位置i的字符是否都等于min_str[i]。

如果有任意字符串在该位置字符不同，则说明最长公共前缀就是min_str[:i]，直接返回。
否则继续检查下一个位置。

如果遍历完min_str的所有字符都没有发现不同，说明min_str本身就是最长公共前缀，返回它。

class Solution:

def longestCommonPrefix(self , strs ):

# write code here

if not strs:

return ""

mins = min(strs,key=len)

for i,ch in enumerate(mins):

for s in strs:

if s[i] != ch:

return mins[:i]

return mins

发表于 2025-09-23 20:46:31 回复(0)

Python3

新生力量

#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
#
# @param strs string字符串一维数组
# @return string字符串
#
class Solution:
    def longestCommonPrefix(self, strs: List[str]) -> str:
        # write code here
        if not strs:
            return ""

        prefix = strs[0]

        for i in range(1, len(strs)):
            while not strs[i].startswith(prefix):
                prefix = prefix[:-1]
                if not prefix:
                    return ""

        return prefix

发表于 2025-09-14 05:00:59 回复(0)

Python3

lintoon

class Solution:

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

# write code here

#排除输入为空列表

if not strs :return ''

m=min(strs)

#排除输入一个元素的列表

if len(strs)==1:return m

#排除最小元素为空字符的列表

if not m: return ""

for i in range(len(m)+1):

for j in strs:

#如当前前缀不同时，输出已确认过的前缀

if m[:i+1]!=j[:i+1]:

return m[:i]

#各元素对应前缀就是列表最小元素m时

else:return m

发表于 2024-04-09 17:02:18 回复(0)

Python3

房子着火我拍照

class Solution:
    def longestCommonPrefix(self , strs: List[str]) -> str:
        if strs == []: return ""
        ms = min(strs)
        for s in strs:
            if s != ms:
                for i in range(len(ms)):
                    if ms[i] != s[i]:
                        ms = ms[:i]
                        break
        return ms

思路：不断缩小最小字符串

编辑于 2024-04-09 11:00:54 回复(0)

Python3

年轻的哈里希望被offer砸中

class Solution:
    def longestCommonPrefix(self, strs: list):
        # write code here
        if len(strs) == 0:
            return ''
        elif len(strs) == 1:
            return strs[0]
        li = strs[0]
        if len(li) == 0:
            return ''
        for i in range(1, len(li) + 1):
            tmp_str = li[:i]
            for str_n in strs[1:]:
                if not str(str_n).startswith(tmp_str):
                    return li[: i - 1]
        else:
            return li

编辑于 2024-02-03 23:40:32 回复(0)

Python3

叮当85

class Solution:
    def longestCommonPrefix(self , strs: List[str]) -> str:
        # write code here
        if len(strs) == 0:
            return ""
        else:
            long_length = len(strs[0])
            i = 1
            while i in range(len(strs)):
                if len(strs[i]) < long_length:
                    long_length=len(strs[i])
                i = i+1
            p = strs[0][0:long_length]
            i =1
            while i in range(len(strs)):
                if strs[i][0:len(p)] == p:
                    i = i+1
                else:
                    p = p[0:len(p)-1]
            return p

发表于 2023-11-07 17:41:49 回复(0)

Python3

牛客429226965号

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

        # 对比两个字符串的最长公共子串
        def cmp(str1, str2):
            index = 0
            while index < len(str1) and index < len(str2):
                if str1[index] != str2[index]:
                    break
                index += 1
            return str1[:index]  # 不包含index

        if len(strs) == 0:
            return ''
        # 初始化result为第一个string
        result = strs[0] 
        # 循环比较数组中的所有字符
        for str1 in strs:
            if str1 == strs[0]:
                continue
            result = cmp(result, str1)
        return result

发表于 2023-08-17 16:21:29 回复(0)

Python3

bcieownnwiJ

class Solution:
    def longestCommonPrefix(self , strs: List[str]) -> str:
        # write code here
        if len(strs) == 0:
            return ''
        pre_str = strs[0]
        for string in strs[1:]:
            if pre_str in string:
                continue
            elif string in pre_str:
                pre_str = string
            else:
                while pre_str not in string:
                    pre_str = pre_str[:-1]
        return pre_str

发表于 2023-04-19 18:07:56 回复(1)

Python3

牛客768556909号

class Solution:
    def longestCommonPrefix(self, strs: List[str]) -> str:
        # write code here
        if not strs:
            return ""
        else:
            res = strs[0]
            for i in range(len(strs) - 1):
                t = strs[i]
                if len(t) < len(res):
                    res = t
            if len(res) > len(strs[-1]):
                res, strs[-1] = strs[-1], res
            r = ""
            for i in range(len(res)):
                if res[i] != strs[-1][i]:
                    break
                else:
                    r += res[i]
            return r

反正是过了

发表于 2023-04-10 15:42:13 回复(0)

Python3

牛客258254114号

class Solution:
    def longestCommonPrefix(self , strs: List[str]) -> str:
        if not strs:
            return ''
        else:
            min_len = min([len(i) for i in strs])
            result = ""
            for j in range(min_len): 
                compare_list = [strs[i][j] for i in range(len(strs))]
                if len(set(compare_list)) == 1:
                    result += strs[0][j]
        return  result

发表于 2022-07-18 23:45:53 回复(0)

Python3

Vivimore

class Solution:
    def longestCommonPrefix(self , strs: List[str]) -> str:
        if not strs:
            return ''
        res = ''
        min_len = min([len(i) for i in strs])
        for i in range(min_len):
            now_s = strs[0][i]
            if all(s[i]==now_s for s in strs):
                res += now_s
            else:
                return res
        return res

发表于 2022-05-26 15:30:50 回复(3)

Python3

Joy_9

class Solution:
    def longestCommonPrefix(self , strs: List[str]) -> str:
        if not strs:
            return ""
        
        def min_pre(a,b):
            long_pre=[]
            for i in range(min(len(a),len(b))):
                if a[i]!=b[i]:
                    break
                else:
                    long_pre.append(a[i])
            return ''.join(long_pre)

        def pre(strs):
            if len(strs) <= 1:
                return strs
            mid=len(strs)//2
            left=pre(strs[:mid])
            right=pre(strs[mid:])
            res=[]
            while len(left)>0 and len(right)>0:
                res.append(min_pre(list(left[0]),list(right[0])))
                right.pop(0)
                left.pop(0)

            if len(left)>0:
                res.extend(left)
            else:
                res.extend(right)
            return res
     
        return pre(strs)[0]

发表于 2022-01-03 07:06:38 回复(0)

Python3

牛客350217643号

class Solution:
def lcp_two(self,str1,str2): # 寻找两个字符串的最长公共前缀
lcp_str = ''
short_ = min(len(str1),len(str2))
for i in range(short_):
if str1[i]==str2[i]:
lcp_str = lcp_str+str1[i]
else:
break
return lcp_str
def longestCommonPrefix(self , strs: List[str]) -> str:
lcp_str='' # 最长公共前缀
if len(strs)==1:
return strs[0]
for i in range(1,len(strs)):
if i==1:
lcp_str = self.lcp_two(strs[i-1],strs[i])
else:
lcp_str = self.lcp_two(lcp_str,strs[i])
return lcp_str

发表于 2021-11-20 15:50:40 回复(0)