# Leetcode 14：Longest Common Prefix 最长公共前缀

Keagan 发布于2019-07-31 10:38 / 516人阅读

摘要：公众号爱写编写一个函数来查找字符串数组中的最长公共前缀。如果不存在公共前缀，返回空字符串。由于字符串长度不一，可以先遍历找出最小长度字符串，这里我选择抛错的形式，减少一次遍历。

公众号：爱写bug

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.

说明:

所有输入只包含小写字母 a-z 。

解题思路Java：

很简单又很经典的一道题，我的思路起先是把第字符串组第一个字符串转为char型。利用StringBuilder逐一累加相同字符。由于字符串长度不一，可以先遍历找出最小长度字符串，这里我选择抛错的形式，减少一次遍历。

代码：

class Solution {
    public String longestCommonPrefix(String[] strs) {
        int strLen=strs.length;
        if(strLen==0) return "";//空字符串组返回""
        char[] temp=strs[0].toCharArray();
        StringBuilder str = new StringBuilder();
        for (int i=0;i
        后面想到Java有 subString() 方法，可指定长度截取字符串，无需转为 char[] 型，但是在 Leetcode 提交时反而不如上面这种方式运算快，这也说明了Java不支持运算符重载，使用 substring() 每次新建一个String字符串，效率并不高。
        最后看到一个方法，大致思路是找到最小长度字符串，从大到小截取字符串，既然用到 subString() 方法，不如就从后向前，因为题目是找出最长公众前缀，从大到小效率很高。具体请看：
 public class Solution {
    public String longestCommonPrefix(String[] strs) {
        if(strs.length==0) return "";
        int min=Integer.MAX_VALUE;
        String minStr="";
        for(int i=0;istrs[i].length()){
                minStr=strs[i];
                min=strs[i].length();
            }
        }
        if(min==0) return "";
        for(int i=min;i>=0;i--){//最小长度字符串从长到短截取
            String standard=minStr.substring(0, i);
            int j=0;
            for(j=0;j
原代码链接： https://blog.csdn.net/qq_14927217/article/details/72955791
解题思路py3：
        再次投机取巧，os.path 封装函数 commonprefix() 一步到位。
代码：
class Solution(object):
    def longestCommonPrefix(self, strs):
        import os
        return os.path.commonprefix(strs)
    其实该函数是利用ASCll码比较的特性来编写的，源码：
def commonprefix(m):
    "Given a list of pathnames, returns the longest common leading component"
    if not m: return ""
    # Some people pass in a list of pathname parts to operate in an OS-agnostic
    # fashion; don"t try to translate in that case as that"s an abuse of the
    # API and they are already doing what they need to be OS-agnostic and so
    # they most likely won"t be using an os.PathLike object in the sublists.
    if not isinstance(m[0], (list, tuple)):
        m = tuple(map(os.fspath, m))
    s1 = min(m)
    s2 = max(m)
    for i, c in enumerate(s1)://枚举得到s1的每一个字符及其索引
        if c != s2[i]:
            return s1[:i]
    return s1
尽管如此，py3这段代码的执行速度依然远比Java慢的多。
注：ASCll码比较大小并非是按照所有字符的ASCll累加之和比较，是从一个字符串第一个字符开始比较大小，如果不相同直接得出大小结果，后面的字符不在比较。

GPU云服务器云服务器最长公共子序列最长公共子串 Common Longest

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/44154.html

# Leetcode 14：Longest Common Prefix 最长公共前缀

摘要：公众号爱写编写一个函数来查找字符串数组中的最长公共前缀。如果不存在公共前缀，返回空字符串。由于字符串长度不一，可以先遍历找出最小长度字符串，这里我选择抛错的形式，减少一次遍历。公众号：爱写bug Write a function to find the longest common prefix string amongst an array of strings. If there...

FrancisSoung 2019-08-16 18:25 评论0 收藏0
leetcode 14 Longest Common Prefix

摘要：题目详情题目要求是，给定一个字符串的数组，我们要找到所有字符串所共有的最长的前缀。为了解决这个问题，可以每次都纵向对比每一个字符串相同位置的字符，找出最长的前缀。题目详情 Write a function to find the longest common prefix string amongst an array of strings. 题目要求是，给定一个字符串的数组，我们要...

suosuopuo 2019-08-16 11:04 评论0 收藏0
leetcode 14 Longest Common Prefix

摘要：题目详情题目要求是，给定一个字符串的数组，我们要找到所有字符串所共有的最长的前缀。为了解决这个问题，可以每次都纵向对比每一个字符串相同位置的字符，找出最长的前缀。题目详情 Write a function to find the longest common prefix string amongst an array of strings. 题目要求是，给定一个字符串的数组，我们要...

jackwang 2019-08-14 18:00 评论0 收藏0
最长公共前缀（LCP）

摘要：最长公共前缀编写一个函数来查找字符串数组中的最长公共前缀。如果不存在公共前缀，返回空字符串。思路先将字符串数组排序，在比较第一个字符串与最后一个字符串的公共前缀即可，只需比较第一个字符串与最后一个字符串保存公共前缀排序不一样则退出循环最长公共前缀 LCP(longest common prefix) Leetcode: 编写一个函数来查找字符串数组中的最长公共前缀。如果不存在公共前缀...

JasonZhang 2019-08-19 11:43 评论0 收藏0
字符串数组最长公共前缀

摘要：字符串数组最长公共前缀给出字符串数组，查找这个数组中所有字符串的最长公共前缀思路从开始自增，判断每个字符串位置的字符是否一致，不一致则之前的串为最长公共字符串。利用函数的特点返回可迭代的对象，只要判断长度大于，则表明此元素非公共字符。字符串数组最长公共前缀 Longest Common Prefix 给出字符串数组，查找这个数组中所有字符串的最长公共前缀 Write a funct...

mrli2016 2019-07-25 12:04 评论0 收藏0