[LeetCode][03] 最长公共前缀

  • 时间:
  • 来源:互联网
  • 文章标签:

题目:

编写一个函数以在字符串数组中找到最长的公共前缀字符串。 如果没有公共前缀,则返回一个空字符串“”

知识点:

  • 列表推导: 减少将一个列表转换为另一个列表时所需编写的代码量

    >>> strs = ["asd", "as", "asfd"]                                                                                        
    >>> [len(s) for s in strs] 
    [3, 2, 4] 
    
  • min()函数: shortest = min(strs,key=len)

    min(iterable, *[, default=obj, key=func]) -> value
    min(arg1, arg2, *args, *[, key=func]) -> value
    使用一个可迭代参数,返回其最小的项。
    如果有两个或多个参数,返回最小的参数。

  • 字符串切片:
    格式:[start: end :step] 从start 提取到end - 1,每step 个字符提取一个
    左侧第一个字符的位置/偏移量为0,右侧最后一个字符的位置/偏移量为-1

  • if …else & return的简写:

            if len(strs) <= 1:
                if len(strs) == 1:
                    return strs[0]
                else:
                    return ""
    

    等价于:

            if len(strs) <= 1:
                return strs[0] if len(strs) == 1 else ""
    
  • enumerate 函数能返回字符串字符和下标

    >>> st="asfjl"                                                                                                          
    
    >>> for index, ch in enumerate(st): 
    ...     print(index, ch)
    ...  
    0 a 
    1 s
    2 f
    3 j
    4 l
    

解题方法:

耗时64ms

	class Solution:
	    def longestCommonPrefix(self, strs: List[str]) -> str:
	        if len(strs) <= 1:
	            return strs[0] if len(strs) == 1 else ""
	        min_len = min([len(s) for s in strs])
	        #注意有空字符串的情况
	        if min_len == 0:
	            return ""
	        end = 0
	        for end in range(min_len):
	            for j in range(1, len(strs)): 
	                if strs[j][end]!= strs[0][end]:
	                    return strs[0][:end]
	         #这个地方字符串切片,end的偏移量的-1,所以这里要加一
	        return strs[0][:end+1]  

耗时48ms

```
class Solution:
    # @param strs: A list of strings
    # @return: The longest common prefix
    def longestCommonPrefix(self, strs):
        # write your code here
        if len(strs) <= 1:
            return strs[0] if len(strs) == 1 else ""
        end, minl = 0, min([len(s) for s in strs])
        while end < minl:
            for i in range(1, len(strs)):
                if strs[i][end] != strs[i-1][end]:
                    return strs[0][:end]
            end = end + 1
        #str[:0]就会自己返回空字符串,所以不用处理minl ==0的情况
        return strs[0][:end]
```

耗时40s,优秀:

```
class Solution:
    def longestCommonPrefix(self, strs: List[str]) -> str:
        if not strs:
            return ""
        shortest = min(strs,key=len)
        for i, ch in enumerate(shortest):
            for other in strs:
                if other[i] != ch:
                    return shortest[:i]
        return shortest 
                
```

本文链接http://www.taodudu.cc/news/show-83183.html