LeetCode–最長公共首碼

LeetCode–最長公共首碼

博客說明

文章所涉及的資料來自互聯網整理和個人總結，意在於個人學習和經驗彙總，如有什麼地方侵權，請聯繫本人刪除，謝謝！

說明

leetcode題，14題

最長公共首碼

題目

編寫一個函數來查找字元串數組中的最長公共首碼。

如果不存在公共首碼，返回空字元串 ""。

示例 1:

輸入: ["flower","flow","flight"]
輸出: "fl"

示例 2:

輸入: ["dog","racecar","car"]
輸出: ""

解釋: 輸入不存在公共首碼。

說明:

所有輸入只包含小寫字母 a-z 

Java

水平掃描法

依次遍歷字元串數組中的每個字元串，對於每個遍歷到的字元串，更新最長公共首碼，當遍歷完所有的字元串以後，即可得到字元串數組中的最長公共首碼。

class Solution {
    public String longestCommonPrefix(String[] strs) {
        if(strs == null || strs.length == 0){
            return "";
        }
        //假設第一個欄位為公共首碼
        String prefix = strs[0];
        int count = strs.length;
        for(int i = 1;i<count;i++){
            //獲取兩個字元串最長首碼
            prefix = longestCommonPrefix(prefix,strs[i]);
            if(prefix.length() == 0){
                break;
            }
        }
        return prefix;
    }

    //獲取兩個字元串最長首碼
    public String longestCommonPrefix(String str1,String str2){
        int length = Math.min(str1.length(),str2.length());
        int index = 0;
        while(index<length && str1.charAt(index) == str2.charAt(index)){
            index++;
        }
        return str1.substring(0,index);
    }
}

Python

水平掃描法

class Solution:
    def longestCommonPrefix(self, strs: List[str]) -> str:
        if not strs:
            return ""
        #假設第一個欄位為公共首碼
        prefix , count = strs[0],len(strs)
        for i in range(1,count):
            #獲取兩個字元串最長首碼
            prefix = self.commonPrefix(prefix,strs[i])
            if not prefix:
                return ""
        return prefix
    #獲取兩個字元串最長首碼
    def commonPrefix(self,str1,str2):
        length,index = min(len(str1),len(str2)),0
        while index < length and str1[index] == str2[index]:
            index += 1
        return str1[:index]
    

C++

水平掃描法

class Solution {
public:
    string longestCommonPrefix(vector<string>& strs) {
        if(!strs.size()){
            return "";
        }

        string prefix = strs[0];
        int count = strs.size();
        for (int i = 1;i < count; i++){
            prefix = longestCommonPrefix(prefix,strs[i]);
            if (!prefix.size()){
                break;
            }
        }
        return prefix;
    }

    string longestCommonPrefix(const string& str1,const string& str2){
        int index = 0;
        int length = min(str1.size(),str2.size());
        while(index < length && str1[index] == str2[index]){
            index++;
        }
        return str1.substr(0,index);
    }
};

PHP

水平掃描法

class Solution {

    /**
     * @param String[] $strs
     * @return String
     */
    function longestCommonPrefix($strs) {
        $prefix = '';
        $i = 0;
      	//判斷其中是否有字元串長度為0
        foreach($strs as $key => $value){
            if($value == ''){
                return $prefix;
            }
        }
        //判斷個數是否為空
        if(count($strs)<1){
            return $prefix;
        }

        while(true){
          	//獲取當前第i個字元
            $current = $strs[0]{$i};
            if(!$current){
                return $prefix;
            }
            foreach($strs as $key => $value){
                if($value{$i} != $current){
                    return $prefix;
                }
            }
            $prefix .= $current;
            $i++;
        }
        return $prefix;
    }
}

感謝

leetcode

以及勤勞的自己

關註公眾號： 歸子莫，獲取更多的資料，還有更長的學習計劃