LeetCode

題目

編寫(xiě)一個(gè)函數(shù)來(lái)查找字符串?dāng)?shù)組中的最長(zhǎng)公共前綴。

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

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

示例 2:
輸入: ["dog","racecar","car"]
輸出: ""
解釋: 輸入不存在公共前綴。

說(shuō)明: 所有輸入只包含小寫(xiě)字母 a-z 。

分析

做這種題對(duì)新手最不友好的是用例覆蓋問(wèn)題, 很多時(shí)候提交了發(fā)現(xiàn)這個(gè)用例不行那個(gè)又行, 而且字符串操作有時(shí)候在C語(yǔ)言還會(huì)報(bào)一些內(nèi)存的錯(cuò), 建議可以先從 Python 找思路.

有大佬評(píng)論總結(jié)一般的用例坑必備以下兩種: 非空判斷(整個(gè)列表為空, 或者內(nèi)部的字符串為一個(gè)或多個(gè)空), 單個(gè)元素判斷(列表只有一個(gè)元素, 或者內(nèi)部字符串只有一個(gè)字符.)
解題的時(shí)候也可以按這個(gè)思路, 先覆蓋上述特殊情況再覆蓋一般情況.

回到本題, 先覆蓋上面的情況, 然后遍歷列表找出字符串最小長(zhǎng)度, 用于判空, 同時(shí)作為外圍循環(huán).
內(nèi)層循環(huán)用列表中字符串個(gè)數(shù), 依次比較每個(gè)字符, 不同則返回, 退出內(nèi)層循環(huán)時(shí)再添加字符到結(jié)果字符串.

實(shí)現(xiàn)

C語(yǔ)言的實(shí)現(xiàn)中注意字符串?dāng)?shù)組創(chuàng)建的寫(xiě)法和初始化.避免越界等問(wèn)題.
筆者查看了C語(yǔ)言版本排在前面的兩個(gè)寫(xiě)法, 時(shí)間復(fù)雜度均為O(m*n), 再次測(cè)試該解法耗時(shí)也回到了 8ms 了.

Python 實(shí)現(xiàn)中也有使用枚舉, zip 函數(shù)實(shí)現(xiàn)的, 看起來(lái)很高大上, 但最后的時(shí)間復(fù)雜度一致, 耗時(shí)也相同.

C實(shí)現(xiàn)

char* longestCommonPrefix(char** strs, int strsSize) {
    if(strsSize==1)
        return strs[0];
    if(strsSize==0)
        return "";
    
    int min_len = strlen(strs[0]);
    for(int i=1; i<strsSize; i++)
    {
        if(strlen(strs[i]) < min_len)
            min_len = strlen(strs[i]);
    }
    if(min_len == 0)
        return "";

    char* str=(char*)malloc(min_len+1);
    memset(str,0,min_len+1);
    
    int i,j=0;
    
    while(1)
    {
        i=0;
        while(i<strsSize-1)
        {
            if(strs[i][j]!=strs[i+1][j])
                return str;
            i++;
        }
        str[j]=strs[0][j];
        if(j==min_len)
            return str;
        j++;
    }
    return str;
}

image.png

Python實(shí)現(xiàn)

class Solution:
    def longestCommonPrefix(self, strs):
        """
        :type strs: List[str]
        :rtype: str
        """
        if len(strs) == 1:
            return strs[0]
        if len(strs) == 0:
            return ""
        
        min_len = min([len(i) for i in strs])
        
        if min_len == 0:
            return ""
        str_list = [list(i) for i in strs]
        result = []
        
        for i in range(min_len):
            for j in range(len(strs)-1):
                if str_list[j][i] != str_list[j+1][i]:
                    return ''.join(result)
            result.append(str_list[j][i])
            if(min_len == i+1):
                return ''.join(result)

image.png

微信公眾號(hào): 程序員的碎碎念