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.
Note:
All given inputs are in lowercase letters a-z.
class Solution {
public:
string longestCommonPrefix(vector<string>& strs)
{
if (strs.size() == 0)
return "";
int max_common = INT_MAX;
string longest_common = "";
for (int i = 0; i < strs.size(); i++)
if (strs[i].size() < max_common)
max_common = strs[i].size();
for (int i = 0; i < max_common; i++) {
for (int j = 1; j < strs.size(); j++) {
if (strs[j][i] != strs[0][i])
return longest_common;
}
longest_common += strs[0][i];
}
return longest_common;
}
};本代码提交AC，用时4MS。
二刷。简洁版代码如下：
class Solution {
public:
string longestCommonPrefix(vector<string>& strs) {
int n = strs.size(), i = 0;
if (n == 0)return "";
while (true) {
bool valid = true;
for (int j = 0; j < n; ++j) {
if (i >= strs[j].size() || strs[j][i] != strs[0][i]) {
valid = false;
break;
}
}
if (!valid)break;
else ++i;
}
return strs[0].substr(0, i);
}
};本代码提交AC，用时4MS。