Longest Common Prefix

昨天接到深信服的电话面试。其中一道很简单的算法题因一时愚蠢没有给出能力范围内的最优解。记录一下，希望以后面试过程中能把每个问题不忙不赶地给出能力范围内的最优答案。

题目描述：

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

拿到这个题首先应该想到，既然求最长公共前缀，那么这个前缀必然不能大于数组中最短的字符串。因此可先求出最短字符串长，再将长度作为下界来遍历数组中的字符串：
如{“ABC”, “ABUFJK”, “ABCOKL”}

一旦遇到同一位置上的字符不相同，就结束比较返回结果。时间复杂度为O(m*n), m 为最长前缀长度。最坏情况下，所有字符串都相等 m 等于字符串长度。

代码如下：

class Solution {
public:
    string longestCommonPrefix(vector<string>& strs) {
        if (strs.empty())
            return "";
        int size = min_element(strs.begin(), strs.end(),
                               [](const string str1,const string str2){
                                   return str1.size() < str2.size();
                               })->size();
        string res = "";
        for (int i = 0; i < size; ++i) {
            char current = strs[0][i];
            for(int j = 0; j < strs.size(); j++) {
                char t = strs[j][i];
                if (current != t) return res;
            }
            res.push_back(current);
        }
        return res;
    }
};

经 @hyss 指正, 该题不必提前求出最短字符串长。只需依次遍历，不满足条件时结束即可。此法仅需在逻辑中加上是否到达某字符串结尾的判断。