1.题目

原题

编写一个函数来查找字符串数组中的最长公共前缀。如果不存在公共前缀，返回空字符串 ""。所有输入只包含小写字母 a-z 。

例子

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

2.解析

这道题最初想的是用动态规划来做，但是发现没有重复的子问题，而且列表里的字符串是不定长的，所以用动态规划不太合适。
这道问题的关键点在于所有字符串同一位置的比较，因此需要用个循环来做。然后考虑是最长公共前缀，因为最长也长不过最短的那个字符串，所以可以提前设定结束条件（小于最短字符串长度时）。一旦有一个不相等的，这个最长公共前缀就可以直接输出了，这个条件比较重要。

3.python代码

class Solution:
    def longestCommonPrefix(self, strs):
        #思路：最长公共子串的长度不会超过
        if not strs:
            return ''
        if len(strs) == 1:
            return strs[0]
        minl = min(len(str_) for str_ in strs)
        end = 0
        while end < minl:
            flag = 0
            for i in range(1, len(strs)):
                if strs[i][end] != strs[i-1][end]:
                    return strs[0][:end]
            end += 1
        return strs[0][:end]