[数据结构与算法][LeetCode]easy - Longest Common Prefix - python

Problem Description:

Write a function to find the longest common prefix string amongst an array of strings.

If there is no common prefix, return an empty string “”.

题目链接

题目要求在给定的string List中找到它们最长的共同前缀。

思路一：

直接法，扫描第一个字符串，与此同时依次扫描其他字符串的同一位置，去判断是否是一样的字符，当遇到不一样的字母的时候就返回当前得到的前缀。

class Solution(object):
    def longestCommonPrefix(self, strs):
        """
        :type strs: List[str]
        :rtype: str
        """
        if not strs:
            return ''
        res = ''
        for i in range(0,len(strs[0])):
            for j in range(1, len(strs)):
                if i >= len(strs[j]) or strs[j][i] != strs[0][i]:
                    return res
            res = res + strs[0][i]
        return res
            

结果如下：

?思路二：

对于字符串数组做一个排序，然后就只需要比较第一个和最后一个的公共前缀即可。

class Solution(object):
    def longestCommonPrefix(self, strs):
        """
        :type strs: List[str]
        :rtype: str
        """
        if not strs:
            return ''
        strs.sort()
        res = ''
        for i in range(0,len(strs[0])):
            if i >= len(strs[-1]) or strs[0][i] != strs[-1][i]:
                return res
            res = res + strs[0][i]
        return res

结果如下：

?Python的sort函数知识点：

sort()?函数用于对原列表进行排序，如果指定参数，则使用比较函数指定的比较函数。函数sort()会默认地按升序排列。

list.sort() 不会返回对象，但会改变原有的list。这点与sorted()不同，sorted()函数会返回一个列表，而sort（）函数是直接在原来的基础上修改。