#include <bits/stdc++.h>
using namespace std;
string longestCommonPrefix(vector<string>& strs) {
string out = "";
if(strs.size() == 0 ){
return out;
}
//find the minimum length string since the longest common prefix can't be more than that length
string minLenStr = strs[0];
for(int i = 1; i < strs.size(); i++){
if(strs[i].length() < minLenStr.length()){
minLenStr = strs[i];
}
}
//loop over all string and match all the starting characters, update the maximum size possible based on the starting matching characters
int end = minLenStr.length();
for(int i = 0; i < strs.size(); i++){
int j = 0;
while(j < end){
if(minLenStr[j] != strs[i][j]){
break;
}
j++;
}
//update the maximum possible size
if(j < end){
end = j;
}
}
return minLenStr.substr(0, end);
}
int main() {
vector<string> vec(4);
vec[0] = "hello";
vec[1] = "hello World";
vec[2] = "hell";
vec[3] = "helloween";
cout << longestCommonPrefix(vec) << endl;
return 0;
}
I2luY2x1ZGUgPGJpdHMvc3RkYysrLmg+CnVzaW5nIG5hbWVzcGFjZSBzdGQ7CgpzdHJpbmcgbG9uZ2VzdENvbW1vblByZWZpeCh2ZWN0b3I8c3RyaW5nPiYgc3RycykgewogICAgc3RyaW5nIG91dCA9ICIiOwogICAgaWYoc3Rycy5zaXplKCkgPT0gMCApewogICAgICAgIHJldHVybiBvdXQ7CiAgICB9CiAgICAvL2ZpbmQgdGhlIG1pbmltdW0gbGVuZ3RoIHN0cmluZyBzaW5jZSB0aGUgbG9uZ2VzdCBjb21tb24gcHJlZml4IGNhbid0IGJlIG1vcmUgdGhhbiB0aGF0IGxlbmd0aAogICAgc3RyaW5nIG1pbkxlblN0ciA9IHN0cnNbMF07CiAgICBmb3IoaW50IGkgPSAxOyBpIDwgc3Rycy5zaXplKCk7IGkrKyl7CiAgICAgICAgaWYoc3Ryc1tpXS5sZW5ndGgoKSA8IG1pbkxlblN0ci5sZW5ndGgoKSl7CiAgICAgICAgICAgIG1pbkxlblN0ciA9IHN0cnNbaV07CiAgICAgICAgfQogICAgfQogICAgLy9sb29wIG92ZXIgYWxsIHN0cmluZyBhbmQgbWF0Y2ggYWxsIHRoZSBzdGFydGluZyBjaGFyYWN0ZXJzLCB1cGRhdGUgdGhlIG1heGltdW0gc2l6ZSBwb3NzaWJsZSBiYXNlZCBvbiB0aGUgc3RhcnRpbmcgbWF0Y2hpbmcgY2hhcmFjdGVycwogICAgaW50IGVuZCA9IG1pbkxlblN0ci5sZW5ndGgoKTsKICAgIGZvcihpbnQgaSA9IDA7IGkgPCBzdHJzLnNpemUoKTsgaSsrKXsKICAgICAgICBpbnQgaiA9IDA7CiAgICAgICAgd2hpbGUoaiA8IGVuZCl7CiAgICAgICAgICAgIGlmKG1pbkxlblN0cltqXSAhPSBzdHJzW2ldW2pdKXsKICAgICAgICAgICAgICAgIGJyZWFrOwogICAgICAgICAgICB9CiAgICAgICAgICAgIGorKzsKICAgICAgICB9CiAgICAgICAgLy91cGRhdGUgdGhlIG1heGltdW0gcG9zc2libGUgc2l6ZQogICAgICAgIGlmKGogPCBlbmQpewogICAgICAgICAgICBlbmQgPSBqOwogICAgICAgIH0KICAgIH0KICAgIHJldHVybiBtaW5MZW5TdHIuc3Vic3RyKDAsIGVuZCk7Cn0KCmludCBtYWluKCkgewoJdmVjdG9yPHN0cmluZz4gdmVjKDQpOwoJdmVjWzBdID0gImhlbGxvIjsKCXZlY1sxXSA9ICJoZWxsbyBXb3JsZCI7Cgl2ZWNbMl0gPSAiaGVsbCI7Cgl2ZWNbM10gPSAiaGVsbG93ZWVuIjsKCQoJY291dCA8PCBsb25nZXN0Q29tbW9uUHJlZml4KHZlYykgPDwgZW5kbDsKCXJldHVybiAwOwp9