0014. Longest Common Prefix.md

题目

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 "".

Example 1:

Input: ["flower","flow","flight"]
Output: "fl"

Example 2:

Input: ["dog","racecar","car"]
Output: ""
Explanation: There is no common prefix among the input strings.

Note:

All given inputs are in lowercase letters a-z.

我的思路

我准备使用startswith()这个函数，它可以用来判断字符串是否以指定字符或子字符串开头。首先，我想到的是遍历第一个字符，在其过程中维护一个res字符串，一开始令其初始化为空。每次从第一个字符串中取出一个字符暂时加到res中，然后遍历原数组中所有字符串，依次用startswith这个函数判断，如果所有的字符串stratswith都为True，那么就保存这个res。

class Solution:
    def longestCommonPrefix(self, strs: List[str]) -> str:
        if not strs:
            return ""
        res = ""
        tem = ""
        for i in range(len(strs[0])):
            tem = tem + strs[0][i]
            for s in strs:
                if not s.startswith(tem):
                    return res
            res = tem
        return res

• 复杂度：O(n*m)

网上思路

对比了一下，我的思路时间复杂度算是比较快的了。想要加快运行速度，在我的思路上稍加一些改动即可。

class Solution:
    def longestCommonPrefix(self, strs: List[str]) -> str:
        n = len(strs)
        if n == 0:
            return ""
        if n == 1:
            return strs[0]
        min_len_string = min(len(i) for i in strs)
        result = ""
        same = True
        for i in range(min_len_string):
            new_letter = strs[0][i]
            for j in strs:
                if j[i] != new_letter:
                    same  = False
                    break
            if not same:
                break
            else:
                result += new_letter
        return result

对比可以发现，网上比我改进的地方主要在于：他首先找到原list中最短的那个字符串，这样可以减少循环比较的次数。