最长公共前缀

LeetCode第十四题

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

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

示例 1:

输入: ["flower","flow","flight"]
输出: "fl"
示例 2:

输入: ["dog","racecar","car"]
输出: ""
解释: 输入不存在公共前缀。
说明:

所有输入只包含小写字母 a-z 。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/longest-common-prefix

思路

先判断特殊情况，即当数组为空，或者数组仅含一个元素时，做出对应处理。
对于一般情况，先比对出前两个字符串的最长公共前缀，然后拿这个前缀去比对之后的字符串，直到前缀长度为0或者到达数组末尾。这个动态变换的公共前缀长度不增。

源代码

char * longestCommonPrefix(char ** strs, int strsSize){
    //思路：将第一个与第二个比对，得到公共前缀，再拿这个公共前缀与第三个比对，以此类推
    if(strsSize == 0)
        return "";
    if(strsSize == 1)
        return strs[0];
    int len = strlen(strs[0]);        //公共前缀长度，初始值为第一个字符串的长度
    int i = 0;
    int j = 0;
    int k = 1;
    for(k = 1;k < strsSize;++k){
        for(i = 0,j = 0;i < len && j < strlen(strs[k]) && strs[0][i] == strs[k][j];++i,++j)
            ;
        len = i;
        if(len == 0)
            break;
    }
    if(len == 0)
        return "";
    else{
        strs[0][len] = '\0';        
        return strs[0];
    }
}

分析

时间复杂度为线性级别，空间复杂度为常数级别。
此算法为了不增加内存消耗，直接将原字符串数组进行了更改。实际上这样做不太合理。更合适的做法应该是申请空间存储最长公共前缀字符串，然后将指向它的指针返回。