leetcode -14. Longest Common Prefix

问题描述： Write a function to find the longest common prefix string amongst an array of strings.

分析：
题目要求为寻找一组字符串的最长相同前缀，如{“abcd”,"abdf","abf"},三个字符串前两位“ab”相同,最长前缀位ab。
解体思路：最长相同前缀一定小于等于最短字符串的长度，故先找到最短字符串，并以此作为被比较对象，若查找某位上字符串与被比较字符串不相同，则比较结束，被比较字符串该位前的字符即为该字符串组的最长相同前缀。
此题需要考虑两种特殊情况：
（1）字符串组为空。此时直接返回“”即可。
（2）字符串组只有一个字符串。这种情况下，最长相同前缀即为该字符串本身。

代码：

#include <stdio.h>
#include <string.h>
#include <stdlib.h>

char* longestCommonPrefix(char** strs, int strsSize);
int main()
{
    char * strs[] = { "abc"，"abd" };
    int strsize = sizeof(strs) / sizeof(char *);
    printf("strsize=%d\n", strsize);
    char *CommonPrefix;
    //char **str = &strs[0];
    int i=0; 
    for ( i = 0; i < strsize;i++)
    {
        printf("strsize[%d]=%d\n",i, strlen(strs[i]));
        printf("strs[%d]=%s\n", i, strs[i]);
    
    }
    
    CommonPrefix=longestCommonPrefix(strs,strsize);
    printf("longestCommonPrefix=%s\n",CommonPrefix);
    system("pause");
    return 0;
}

char* longestCommonPrefix(char** strs, int strsSize) {
    if (strs == NULL || *strs == NULL) {
        return "";
    }
    if (strsSize==1)
        return *strs;
    int i,j,x=0;
    int minprefix=strlen(strs[0]);  //strs 为二级指针也就是，指针的指针。其实质是一个指针数组，即元素均为指针的数组，数组的数组名表示数组首个元素的地址，而首个元素又是指针，因此指针数组的数组名就是一个二级指针。
    char temp;
    char *result;

    for(i=1;i<strsSize;i++)   //查找最短字符串，并记录其长度
    {
        if(minprefix>strlen(strs[i]))
        {   minprefix=strlen(strs[i]);  
            x=i;
        }
    }
    
    for (j=0;j<minprefix;j++)   //以最短字符串长度为比较位数上限
    { 
        temp=*(strs[x]+j);      //将最短字符串最为基准
        for(i=0;i<strsSize;i++)
        {
    
            if(*(strs[i]+j)!=temp)  //若找到有一位字符不相同，则比较结束
                break;              
        }
        if(i!=strsSize)  //各字符串中至少有两个相应位不同，结束循环
            break;
    }
   
    if(j>=0)           
    {
        result = (char* ) malloc(sizeof(char) *(j+1));
        strncpy(result,strs[x],j+1);          //将相同的前j位返回
        result[j]='\0';
    
    }
    return result;
}

char* longestCommonPrefix(char** strs, int strsSize) {
    if (strs == NULL || *strs == NULL) {
        return "";
    }
    int len = strlen(strs[0]);
    int max = 0;
    char *res;
    while (max < len) {
        for (int i = 1; i < strsSize; i++) {
            if (strs[i][max] != strs[0][max])    //逐位比较，直到找到不同位
            {        
                len = max;
                break;
            }
        }
        if (max < len) max++;      //发现不同位
    }
    res = (char*)malloc(sizeof(char)*(max+1));
    for (int i = 0; i < max; i++)           //将相同的前max位返回
    {
        res[i] = strs[0][i];
    }
    res[max] = '\0';
    return res;
}

参考文献
[1] https://www.oschina.net/question/253203_243676
[2] https://ybzbxcc.github.io/2016/08/06/LeetCode-14-Longest-Common-Prefix/