# Leetcode 14：Longest Common Prefix 最長公共前綴

Keagan 發(fā)布于2019-07-31 10:38 / 517人閱讀

摘要：公眾號愛寫編寫一個函數(shù)來查找字符串?dāng)?shù)組中的最長公共前綴。如果不存在公共前綴，返回空字符串。由于字符串長度不一，可以先遍歷找出最小長度字符串，這里我選擇拋錯的形式，減少一次遍歷。

公眾號：愛寫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 "".

編寫一個函數(shù)來查找字符串?dāng)?shù)組中的最長公共前綴。

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

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：

? 很簡單又很經(jīng)典的一道題，我的思路起先是把第字符串組第一個字符串轉(zhuǎn)為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() 方法，可指定長度截取字符串，無需轉(zhuǎn)為 char[] 型，但是在 Leetcode 提交時反而不如上面這種方式運(yùn)算快，這也說明了Java不支持運(yùn)算符重載，使用 substring() 每次新建一個String字符串，效率并不高。
?        最后看到一個方法，大致思路是找到最小長度字符串，從大到小截取字符串，既然用到 subString() 方法，不如就從后向前，因?yàn)轭}目是找出最長公眾前綴，從大到小效率很高。具體請看：
 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：
?        再次投機(jī)取巧，os.path 封裝函數(shù) commonprefix() 一步到位。
代碼：
class Solution(object):
    def longestCommonPrefix(self, strs):
        import os
        return os.path.commonprefix(strs)
?    其實(shí)該函數(shù)是利用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這段代碼的執(zhí)行速度依然遠(yuǎn)比Java慢的多。
注：ASCll碼比較大小并非是按照所有字符的ASCll累加之和比較，是從一個字符串第一個字符開始比較大小，如果不相同直接得出大小結(jié)果，后面的字符不在比較。