2019-07-01 385 views 评论

Leetcode 14：最长公共前缀

题目描述

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

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

示例

示例1：

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

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

输出: "fl"

示例2：

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

输入: ["dog","racecar","car"]

输出: ""

解释: 输入不存在公共前缀。

题目解析

我的思路是，首先对所有的字符串进行排序，因为存入了vector，所以直接使用sort排序即可。然后，寻找第一个字符串和最后一个字符串的最大公共前缀，就是整个数组的公共前缀。
当然，要考虑一些特殊情况：
1. 数组中是一个或一个以上空字符串。
2. 数组为空。
具体解决方法在下面的代码已经体现。

代码实现

string longestCommonPrefix(vector&lt;string&gt;&amp; strs) {
    string res;
    int strslen = strs.size();
    if (strslen &lt; 1)
        return res;
    else if (strslen == 1)
        return strs[0];
    sort(strs.begin(), strs.end());
    int i = 0;
    for (int i = 0; i &lt; strslen; i++)
    {
        if (strs[i].size() == 0)
            return res;
    }
    int llen = strs[0].size();
    int rlen = strs[strslen - 1].size();
    int mlen = min(llen, rlen);//保证比较最小的长度
    while (strs[0][i] == strs[strslen - 1][i])
    {
        res += strs[0][i];
        if (i &lt; mlen)//如果已经达到最小长度就退出
            ++i;
        else
            break;
    }
    return res;
}