一、题目

编写一个函数来查找字符串数组中的最长公共前缀。如果不存在公共前缀,返回空字符串 ""。

示例 1:

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

示例 2:

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

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


二、解决方法

方法一:水平扫描(逐个字符串进行比较)

思路:首先将第一个字符串作为ans,然后依次与后面的每一个字符串比较并更新ans,若某一趟途中ans为空,即没有公共前缀,直接返回。这样,最后得到的ans即为所求。
代码如下

char* longestCommonPrefix(char** strs, int strsSize) 
{
    if (strsSize == 0)
        return "";
    char* ans = strs[0];
    int i, j;
    for (i = 1; i < strsSize; i++)
    {
        j = 0;
        for ( ; ans[j] != '\0' && strs[i][j] != '\0'; j++)
        {
            if (ans[j] != strs[i][j])
                break;
        }
        ans[j] = '\0';
        if (ans == NULL)
        {
            return "";
        }
    }
    return ans;
}

方法二:水平扫描(对字符串中的每一列字符进行比较)

思路:以第一个字符串为基准,分别将后面每一个字符串中的每一列与第一个字符串对应列位置的字符进行比较,如果都相等,则对后面对应列的字符进行比较;反之,设置第一个字符串该列所在位置字符为结束字符并退出循环返回第一个字符串。
代码如下

char* longestCommonPrefix(char** strs, int strsSize) 
{
    if (strsSize == 0)
        return "";
    for (int i = 0; i < strlen(strs[0]); i++)
    {
        for (int j = 0; j < strsSize; j++)
        {
            if (strs[0][i] != strs[j][i])
            {
                strs[0][i] = '\0';
                break;
            }
        }
    }
    return strs[0];
}