Write a function to find the longest common prefix string amongst an array of strings.

If there is no common prefix, return an empty string "".

Example 1:

Input: ["flower","flow","flight"]
Output: "fl"
Example 2:

Input: ["dog","racecar","car"]
Output: ""
Explanation: There is no common prefix among the input strings.

char* longestCommonPrefix(char** strs, int strsSize) 
{
    if(strsSize < 1)
        return "";
    
    int minlen = INT_MAX;
    int len = 0;
    int k = 0;
    char c;
    
    /*计算字符串最小长度*/
    for(int i=0;i<strsSize;i++)
    {
        int len = strlen(strs[i]);
        if(len < minlen)
            minlen = len;
    }
    
    /*申请内存保存结果*/
    char *res =(int *)malloc(sizeof(char) *(minlen+1));
    memset (res,'\0',minlen+1);
    
    for(int i=0;i<minlen;i++)
    {
        c = strs[0][i];
        for(int j=1;j<strsSize;j++)
        {
            if(strs[j][i]!=c)
                return res;
        }
        res[k++] = c;
    }
    
    return res;
    
}

C++实现

class Solution {
public:
    string longestCommonPrefix(vector<string>& strs) {
        int n = strs.size();
        if(n <= 0) return "";

        string s = strs[0];
        for(int i = 0;i < s.size();i++)
        {
            for(int j = 1;j < n;j++)
            {
                if(strs[j][i] != s[i])
                {
                    if(i == 0) return "";
                    else return s.substr(0,i);
                }
            }
        }

        return s;
    }
};

优化后的写法：

class Solution {
public:
    string longestCommonPrefix(vector<string>& strs) {
        string prefix = "";
        
        for(int idx = 0;strs.size()>0;prefix += strs[0][idx],idx++)
        {
            for(int i = 0;i < strs.size();i++)
            {
                if(idx >= strs[i].size() || (i > 0) && strs[i-1][idx]!=strs[i][idx])
                    return prefix;
            }
        }
        
        return prefix;
    }
};