【Leetcode】14—Longest Common Pref

一、题目描述

编写一个函数来查找字符串数组中的最长公共前缀。如果不存在公共前缀，返回空字符串 ""
示例：

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

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

二、代码实现

方法一：比较多个字符串的最长公共前缀，实际上只需要比较最大和最小的，只要最大和最小有共同前缀，其他中间都有。这里的最大最小是把字符串中每个字符的ASCII码相加，分别找出最大和最小。

class Solution(object):
    def longestCommonPrefix(self, strs):
        """
        :type strs: List[str]
        :rtype: str
        """
        if len(strs) == 0: return ""
        if len(strs) == 1: return strs[0]
        minstr = min(strs)
        maxstr = max(strs)
        
        commonstr = ""
        strlen = min(len(minstr), len(maxstr))
        for idx in range(strlen):
            if minstr[idx] == maxstr[idx]:
                commonstr = commonstr + minstr[idx]
            else:
                break
        return commonstr

方法二：使用os.path.commonprefix

class Solution(object):
    def longestCommonPrefix(self, strs):
        """
        :type strs: List[str]
        :rtype: str
        """
        return os.path.commonprefix(strs)

方法三：使用zip，将字符串拆分成字符，逐个比较

class Solution(object):
    def longestCommonPrefix(self, strs):
        """
        :type strs: List[str]
        :rtype: str
        """
        commonpath = ""
        for chars in zip(*strs):
            if len(set(chars)) == 1:
                commonpath = commonpath + chars[0]
            else:
                break        
        return commonpath