描述

给你一个大小为 n 的字符串数组 strs ，其中包含n个字符串 , 编写一个函数来查找字符串数组中的最长公共前缀，返回这个公共前缀。

数据范围： 0 \le n \le 50000≤n≤5000， 0 \le len(strs_i) \le 50000≤len(strsi)≤5000
进阶：空间复杂度 O(1)O(1)，时间复杂度 O(n*len)O(n∗len)

示例1

输入： 
["abca","abc","abca","abc","abcc"]
复制
返回值： 
"abc"
复制

示例2

输入： 
["abc"]
复制
返回值： 
"abc"
复制

解题思路：
1、先将字符串数组排序，这样公共子串最长就是第一个字符串；
2、以第一个字符串为基准与后面的字符串逐字符比较，相等的加入结果字符串，遇到第一个不相等的即可返回；
3、注意入参有效性及特殊情况的判断。 

class Solution {
public:
    /**
     * 
     * @param strs string字符串vector 
     * @return string字符串
     */
    string longestCommonPrefix(vector<string>& strs) {
        // write code here
        int len = strs.size();
        if (len <= 0) return "";
        if (len == 1) return strs[0];
        sort(strs.begin(), strs.end());
        string s = "";
        for (int i = 0; i < strs[0].size(); i++) {
            for (int j = 1; j < len; j++) {
                if (strs[0][i] != strs[j][i]) {
                    return s;
                }
            }
            s += strs[0][i];
        }
        return s;
    }
};