# Leetcode 14：Longest Common Prefix 最長公共字首

公衆号：愛寫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<strs[0].length();i++){//以第一個字元串長度開始比較
            for (int j=1;j<strLen;j++){
                try {
                    if(temp[i]!=strs[j].charAt(i)){
                        return str.toString();
                    }
                }catch (IndexOutOfBoundsException e){//抛出錯誤，這裡錯誤是指索引超出字元串長度
                    return strs[j];
                }
            }
            str.append(temp[i]);
        }
        return strs[0];
    }
}           

​ 後面想到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;i<strs.length;i++){//找出最小長度字元串
            if(min>strs[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<strs.length;j++){
                if(strs[j].substring(0, i).equals(standard)) continue;
                else break;
            }
            if(j==strs.length) return standard;
        }
        return "";
    }
}           

原代碼連結：

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累加之和比較，是從一個字元串第一個字元開始比較大小，如果不相同直接得出大小結果，後面的字元不在比較。