Leetcode 最长公共前缀

地址：https://leetcode-cn.com/explore/interview/card/top-interview-questions-easy/5/strings/40/

题目

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

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

示例 1:

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

示例 2:

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

说明:

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

我的解决方案

刚读完题就诞生了两个解题思路，所以都尝试写了一下，确实也都是可行的方法。

相对来说，如果公有部分较长的话应该方法二会高效一些，反之方法一可能更高效。个人感觉方法二应该更普适。

方法一：

这个方法比较容易想到，因为要找的是公共前缀，也就是所有字符串有有的前缀，所以从每个字符串的第1个元素开始判断是否都相等，相等则将这个字符插入到返回字符串str，直到找到某个字符不是所有字符串的公共部分，则不再插入到返回值str，并且后续无需继续判断。此时得出的字符串str就是字符串数组的公共前缀。

缺点：如果公共前缀太长的话，会做公共前缀对应长度的无效益的循环用于判断是否这些字符是否是公共的。

class Solution {
public:
    string longestCommonPrefix(vector<string>& strs) {
        string str = "";   //返回值，初始化为空字符串
        if (strs.size() > 0) {   //strs为空的话直接执行return语句返回空字符串，否则执行下面的部分
            for (int j = 0;; j++) {
                if (j >= strs[0].size())   //因为总是从第一个字符串开始，所以第一个字符串遍历完后后续就不可能再存在公有的字符了
                    break;
                else {
                    char ch = strs[0][j];    //字符串str[0]的第j+1个字符
                    bool bl = true;     //字符ch是否公有的标志
                    for (int k = 0; k < strs.size(); k++) {
                        if (strs[k][j] != ch) {   //如果某个字符串的第j个字符和ch不同说明ch不是公有字符
                            bl = false;
                            break;
                        }
                    }
                    if (bl == true)   //说明ch是公有字符，插入到str尾部
                        str.insert(str.end(), ch);
                    else break;   //说明ch不是公有字符，后续不需要再判断
                }
            }
        }
        return str;
    }
};

方法二：

这个方法感觉高效一些，正好弥补了方法一的缺点。

思路是，任选一个字符串作为初始的str（为了方便遍历字符串数组，所以选第一个字符串strs[0]作为初始值），然后用其余每一个字符串依次和str比较查找公共部分，然后删去非公共部分，当整个字符串数组遍历完的时候也就删掉了字符串str与其余所有字符串的非公共部分，剩下的就是公共部分也就是所有字符串的公共前缀。

class Solution {
public:
    string longestCommonPrefix(vector<string>& strs) {
        string str = "";   //返回值，初始化为空字符串
        if (strs.size() > 0) {
            str = strs[0];   //strs至少有一个字符串strs[0]，用它初始化str，因为公有部分的长度一定小于strs中的任意一个字符串
            if (strs.size() > 1) {  //如果strs.size（）大于1，则需要判断字符串str的哪部分为公有的
                for (int i = 1; i < strs.size(); i++) {  //从第二个字符串开始依次与str比较寻找公有部分，并删除str的非公有部分
                    int size = str.size() < strs[i].size() ? str.size() : strs[i].size();
                    str.erase(str.begin() + size, str.end());  //如果str更长一些可以直接删除多余部分
                    for (int j = 0; j < size; j++) {
                        if (str[j] != strs[i][j]) {   //某一个字符不相等说明从这个字符开始的后面所有字符都是多余的，删除即可
                            str.erase(str.begin() + j, str.end());
                            break;
                        }
                    }
                }
            }
        }
        return str;
    }
};

测试数据

测试1：
flower
flow
flight

测试2：
dog
racecar
car

测试数据需要考虑下数组为空的情况以及strs数组大小为1的较特殊情况。