About

因为前几天出去旅游了，好几天没更文了，今天先做一道简单题起手，开始学习。

最长公共前缀

题目描述

编写一个函数来查找字符串数组中的最长公共前缀。

如果不存在公共前缀，返回空字符串 ""。

示例 1:

输入: ["flower","flow","flight"]
输出: "fl"

示例 2:

输入: ["dog","racecar","car"]
输出: ""
解释: 输入不存在公共前缀。

说明:
所有输入只包含小写字母 a-z 。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/longest-common-prefix

解题思路

一般来说我们一看到这种简单的题就有思路，但是我们会考虑的问题是如何让算法的效率更高，先说一种暴力解法——扫描法：从第一个元素到最后一个元素循环比较对应位置的字符是否相等，如果不相等就返回上一次循环的字符串。

代码

class Solution:
    def longestCommonPrefix(self, strs):
        length = len(strs)
        if length == 0: return ''  # 处理边界情况 
        counter = 0
        while True:
            try:    # 使用try来处理list out of range的异常
                for i in range(length):
                    if strs[0][counter] != strs[i][counter]:    # 循环比较每个对应位置的字符
                        return strs[0][0:counter]   # 不相等就返回上一次循环的列表切片
                counter += 1
            except BaseException:
                return strs[0][0:counter]   # 处理异常

运行结果

扫描法结果

思路二

利用sort()方法会产生比较有意思的作用，sort()会从头开始按照字符串的字符在字母表中的位置进行排序，比如：['b','bc','ba','a','c'].sort()结果为['a', 'b', 'ba', 'bc', 'c']，无论列表中的元素是否含有公共前缀，我们只需要比较第一个元素和最后一个元素的对应位置是否相等就可以得出最长公共前缀。（我感觉我说不清楚，但能想明白）

代码

class Solution:
    def longestCommonPrefix(self, strs):
        if len(strs) == 0:    return ''
        if len(strs) == 1:    return strs[0]    # 处理边界情况
        strs.sort()     # 将列表进行排序，排序是按照字符在字母表中的位置排序
        comms = ''
        for x,y in zip(strs[0],strs[-1]):   # 使用zip形成对应位置的元组
            if x == y:
                comms += x  # 如果对应位置字符相等就将该字符拼接到公共前缀中
            else:
                break
        return comms

运行结果

思路二结果