Lintcode: Longest Common Prefix

Given k strings, find the longest common prefix (LCP).

Have you met this question in a real interview?

Yes

Example

For strings "ABCD", "ABEF" and "ACEF", the LCP is "A"

For strings "ABCDEFG", "ABCEFG" and "ABCEFA", the LCP is "ABC"

Tags Expand 

Enumeration Basic Implementation String

Thought:
Check letter of the same position from strings one by one.
m -- length of the longest common prefix
n -- number of strings
Time: O(mn)
Space: O(m)

class Solution {
public:    
    /**
     * @param strs: A list of strings
     * @return: The longest common prefix
     */
    string longestCommonPrefix(vector<string> &strs) {
        // write your code here
        string res;
        if(strs.size() == 0) return res;
        for(int i = 0; i < strs[0].size(); i++){
            char c = strs[0][i];
            for(int j = 0; j < strs.size(); j++){
                if(strs[j][i] != c) return res;
            }
            res += c;
        }
        return res;
    }
};

Another way is to keep comparing strings to get final prefix.
m -- average length of each string  n-- number of strings
Time: O(mn)
Space: O(m)

class Solution {
public:    
    /**
     * @param strs: A list of strings
     * @return: The longest common prefix
     */
    string longestCommonPrefix(vector<string> &strs) {
        // write your code here
        string prefix;
        if(strs.size() == 0) return prefix;
        prefix = strs[0];
        for(int i = 1; i < strs.size(); i++){
            for( int j = 0; j < prefix.size(); j++){
                if(strs[i][j] != prefix[j]){
                    prefix = prefix.substr(0, j);
                }
            }
        }
        return prefix;
    }
};

Reference: http://www.cnblogs.com/TenosDoIt/p/3856331.html