14.Longest Common Prefix

题目：最长共同子串

Write a function to find the longest common prefix string amongst an array of strings.

If there is no common prefix, return an empty string “”.

Example 1:

Input: [“flower”,“flow”,“flight”]
Output: “fl”

Example 2:

Input: [“dog”,“racecar”,“car”]
Output: “”
Explanation: There is no common prefix among the input strings.
方法一:直接比较

class Solution {
public:
    string longestCommonPrefix(vector<string>& strs) {
        if(strs.empty()) return "";
        string res="";
        for(int i=0;i<strs[0].size();i++)
        {
            char c=strs[0][i];
            for(int j=1;j<strs.size();j++)
            {
                if(i>strs[j].size() || strs[j][i]!=c)
                    return res;
            }
            res.push_back(c);
        }
        return res;
    }
};

方法二：将字符串按顺序排列，则有相同字符的字符串居中，而不相同最多的字符在两端，所以直接检索首尾字符串

class Solution {
public:
    string longestCommonPrefix(vector<string>& strs) {
        if(strs.empty()) return "";
        sort(strs.begin(),strs.end());
       int length=min(strs[0].size(),strs.back().size());
        int i=0;
        while(i<length && strs[0][i] == strs.back()[i])
            ++i;
        return strs[0].substr(0,i);
    }
};