LeetCode-Algorithms-14.最长公共前缀

1. 题目描述

编写一个函数来查找字符串数组中的最长公共前缀。

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

示例 1:   
            输入: ["flower","flow","flight"]
            输出: "fl"
示例 2:   
            输入: ["dog","racecar","car"]
            输出: ""
解释: 输入不存在公共前缀。
说明:所有输入只包含小写字母 a-z 。

2. 提交记录

14.最长公共前缀.png

3. 算法思想

当字符串的长度 strsSize 为 0 时，返回空串；
当字符串的长度 strsSize 为 1 时，返回该字符串；
当字符串的长度 strsSize 大于1时，比较第一和第二个字符串的长度，取较小的一个作为循环次数。如果字符串char ** strs当中有空串，直接返回空串 “” 不再进行比较查找。

4. 代码实现

    char * longestCommonPrefix(char ** strs, int strsSize){
        char * str = (char *)malloc(128 * sizeof(char));  //用来存储公共前缀
        memset(str, 0, 128);
    
        if (strsSize == 0 )
        {
            return "";
        }
        strcpy(str, strs[0]);
        
        if(strsSize == 1){
            return str;
        }
           
        int len = strlen(str);      //用来计算公共前缀的长度
        
        if(len > strlen(strs[1])){
            len = strlen(strs[1]);
        }
        for (int i = 1; i < strsSize; i++)
        {
            if(strlen(strs[i]) == 0){
                return "";
            }
            char * currentStr = strs[i];
            int j;
            for (j = 0; j < len; j++)
            {
                if (str[j] != currentStr[j])
                {
                    break;
                }
            }
            len = j;
            str[j] = '\0';
        }
        return str;     
    }