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