LeetCode刷题：最长公共前缀

最长公共前缀

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

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

示例 1：

输入：strs = ["flower","flow","flight"]
输出："fl"
示例 2：

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

python解法

解法一

字符串本身按位排序后，只需要针对第一个和最后一个字符串进行比较就能获取最终答案。
相比于纵向查找，看似只比较了第一个和最后一个，但是排序也是消耗时间的。

class Solution(object):
    def longestCommonPrefix(self, strs):
        strs.sort()
        lg = min(len(strs[0]), len(strs[-1]))
        ret = ""
        for i in range(lg):
            if strs[0][i] != strs[-1][i]:
                break
            ret += strs[0][i]
        return ret

解法二

class Solution:

def longestCommonPrefix(self, strs: List[str]) -> str:

pre_str = ''

for i in zip(*strs):

if len(set(i)) == 1:

pre_str += i[0]
else:
break
return pre_str

java解法

class Solution {
    public static String longestCommonPrefix(String[] strs) {
        int strs_len=strs.length;
        String s=strs[0];
        //循环将所得的最长公共前缀与数组中其他字符求其最长公共前缀，并更新最长公共前缀
        for(int i=1;i<strs_len;i++){
            s=Prefix(s,strs[i]);
        }
        return s;
    }
    //求出两个字符串的最长公共前缀，并将该前缀返回
    public static String Prefix(String str1,String str2){
        char[] c1=str1.toCharArray();
        char[] c2=str2.toCharArray();
        int i,j;
        int len=c1.length>c2.length ? c2.length:c1.length;
        for(i=0;i<len;i++){
            if(c1[i]!=c2[i])
                break;
        }
        String s= String.valueOf(str1.subSequence(0,i));
        return s;
    }
}