最长公共前缀

思路

输入：strs= ["flower","flow","flight"]

输出："fl"

由用例可知，每个字符串的长度可能不同，所以可以想到，最长公共前缀一定小于这些字符串中最短的那个，可用minL表示最短长度，即每个字符串只需要遍历到minL - 1即可。在该用例值minL为4，strsSize为3

所以为了判断某个字符是否“公共”，则需要按如下次序判断:

第一趟               第二趟        第三趟

flowerflower    flower

flowflow            flow

flightflight    flight

由上可知，第一趟中三个字符串的第一个字符都是f，第二趟的第二个字符都是l，第三趟的第三个字符出现了不同。

由上句加粗字体可得

第一趟判断的字符为,strs[0][0],strs[1][0],strs[2][0]

第二趟判断的字符为,strs[0][1],strs[1][1],strs[2][1]                    strs[行][列]

第二趟判断的字符为,strs[0][2],strs[1][2],strs[2][2]

我们一搬遍历都是先行后列，而这次需要先列后行。

因此需要控制列不变，行变。

列数即字符串的长度，则最长公共前缀都小于等于minL。因此可得如下代码。

代码

char*longestCommonPrefix(char**strs, intstrsSize){
//用flag来控制前缀是否已找到，count用于表示前缀的数目，minL表示最短字符串intflag,count=0,minL=200;
for(inti=0; i<strsSize; i++)
if(strlen(strs[i]) <minL)minL=strlen(strs[i]);
for(inti=0; i<minL; i++){
flag=1;
for(intj=0; j<strsSize-1; j++){
//当flag = 0则表明最长公共前缀已经找到if(strs[j][i] !=strs[j+1][i]){
flag=0;
//两个break退出双重for循环break;
            }
        }
//flag = 1则表明strs[i][count]为公共前缀之一if(flag)count++;
elsebreak;
    }
//用'\0'来表示字符串的结束strs[0][count] ='\0';
returnstrs[0];
}

大家若有其他方法，欢迎交流。