14. 最长公共前缀

难度：简单

题目

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

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

示例 1：

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

示例 2：

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

说明：

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

Reference

题解

基本思路： 在比较前缀时只需要将前 n 个字符串的公共前缀与第 n+1 个字符串进行比较。

代码如下：

char *compareTwo(char *str1, char *str2)
{
    char *cur1 = str1, *cur2 = str2, *ret = NULL;
    int len = 0;
    while (*cur1 && *cur2)
    {
        if (*cur1 != *cur2)
            break;
        else
            len++;
        cur1++;
        cur2++;
    }
    ret = (char *)memset(malloc(sizeof(char) * (len + 1)), 0, sizeof(char) * (len + 1));
    return memcpy(ret, str1, sizeof(char) * len);
}

char * longestCommonPrefix(char ** strs, int strsSize){
    if (strsSize == 0)
        return memset(malloc(sizeof(char)), 0, sizeof(char));
    if (strsSize == 1)
        return strs[0];
    if (strsSize == 2)
        return compareTwo(strs[0], strs[1]);
    int rec_size = (strsSize + 1) >> 1, i = 0;
    char **rec = (char **)memset(malloc(sizeof(char *) * rec_size), 0, sizeof(char *) * rec_size);
    for (i = 0; i < strsSize >> 1; i++)
        rec[i] = compareTwo(strs[2 * i], strs[2 * i + 1]);
    if (strsSize & 1)
        rec[rec_size - 1] = strs[strsSize - 1];
    return longestCommonPrefix(rec, rec_size);
}

评论