fork download
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. string longestCommonPrefix(vector<string>& strs) {
  5. string out = "";
  6. if(strs.size() == 0 ){
  7. return out;
  8. }
  9. //find the minimum length string since the longest common prefix can't be more than that length
  10. string minLenStr = strs[0];
  11. for(int i = 1; i < strs.size(); i++){
  12. if(strs[i].length() < minLenStr.length()){
  13. minLenStr = strs[i];
  14. }
  15. }
  16. //loop over all string and match all the starting characters, update the maximum size possible based on the starting matching characters
  17. int end = minLenStr.length();
  18. for(int i = 0; i < strs.size(); i++){
  19. int j = 0;
  20. while(j < end){
  21. if(minLenStr[j] != strs[i][j]){
  22. break;
  23. }
  24. j++;
  25. }
  26. //update the maximum possible size
  27. if(j < end){
  28. end = j;
  29. }
  30. }
  31. return minLenStr.substr(0, end);
  32. }
  33.  
  34. int main() {
  35. vector<string> vec(4);
  36. vec[0] = "hello";
  37. vec[1] = "hello World";
  38. vec[2] = "hell";
  39. vec[3] = "helloween";
  40.  
  41. cout << longestCommonPrefix(vec) << endl;
  42. return 0;
  43. }
Success #stdin #stdout 0s 15240KB
stdin
Standard input is empty
stdout
hell