14. Longest Common Prefix

Given an array of strings, the problem is to find out the longest common prefix of all the strings.

Return empty string if no common prefix exists.

Approach:
Use the brute force way approach to solve the problem. First find the shortest string (as the longest common prefix can be of at most this length), minLenStr, which takes O(n) time. Next, compare each string one by one with this minLenStr, and keep an variable which indicates the rightmost index of minLenStr, this loop takes O(mn) where m is the shortest length of all strings.

class Solution {
public:
    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);
    }
};

Here is the link to the ideone solution : http://ideone.com/CWFcI8