题目

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

分析

思路很简单，就是首先比较每个字符串的第一个字母，都相同再比较下一个。当有不相同或者到达某个字符串的末端时结束，输出结果。

实现

class Solution {
public:
    string longestCommonPrefix(vector<string>& strs) {
        if(strs.empty()) return string("");
        if(strs.size()==1) return strs[0];
        int minSize=INT_MAX, i;
        bool over = false;
        for(i=0; !over; i++){
            bool stop = false;
            char ch = strs[0][i];
            for(int j=1; j<strs.size(); j++){
                if(i>=strs[j].size()){
                    over = true;
                    break;
                }
                if(strs[j][i]!=ch){
                    stop = true;
                    break;
                }
            }
            if(stop||over) break;
        }
        return strs[0].substr(0,i);                                          
    }
};

思考

这题一开始被空数据坑了。看来要多考虑这些特殊情况啊。
另外还有更漂亮的写法（题解）。

class Solution{
  public:
    string longestCommonPrefix(vector<string> &strs){
        if (strs.empty())
            return "";
        for (int idx = 0; idx < strs[0].size(); ++idx){
            for (int i = 1; i < strs.size(); ++i){
                if (strs[i][idx] != strs[0][idx])
                    return strs[0].substr(0, idx);
            }
        }
        return strs[0];
    }
};