原题描述
Write a function to find the longest common prefix string amongst an array of strings.
算法
这个题有两种直接的算法：
1. “字符串间匹配（横向比较）”. 取第一个字符串和其他的字符串两两比较，得到两两比较中的最长公共前缀. 这一种算法不是最优的，可以假设只有最后一个字符串和其余的不同，那么之前的字符串比较都是在浪费时间，所以说不是最优的
2. “字符匹配（纵向匹配）”. 在所有字符串中从左到右进行匹配，一旦发现不匹配的就退出，这样可以大幅度减少比较的时间。
C++代码
class Solution {
public:
string longestCommonPrefix(vector<string>& strs) {
if (strs.size() == 0) return "";
string prefix = "";
for (int idx = 0; idx < strs[0].length() ; prefix+=strs[0][idx] , idx++){
for(int i=1; i<strs.size(); i++)
if(idx >= strs[i].size() || (i > 0 && strs[i][idx] != strs[0][idx]))
return prefix;
}
return prefix;
}
};
Bug Free Procedure 从记事本直接写代码
2016.12.13 Bingo！！！一次性AC