# C++实现LeetCode(14.最长共同前缀)

[LeetCode] 14. Longest Common Prefix 最长共同前缀

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.

C++ 解法一：

```class Solution {
public:
string longestCommonPrefix(vector& strs) {
if (strs.empty()) return "";
string res = "";
for (int j = 0; j < strs[0].size(); ++j) {
char c = strs[0][j];
for (int i = 1; i < strs.size(); ++i) {
if (j >= strs[i].size() || strs[i][j] != c) {
return res;
}
}
res.push_back(c);
}
return res;
}
};```

Java 解法一：

```public class Solution {
public String longestCommonPrefix(String[] strs) {
if (strs == null || strs.length == 0) return "";
String res = new String();
for (int j = 0; j < strs[0].length(); ++j) {
char c = strs[0].charAt(j);
for (int i = 1; i < strs.length; ++i) {
if (j >= strs[i].length() || strs[i].charAt(j) != c) {
return res;
}
}
res += Character.toString(c);
}
return res;
}
}```

C++ 解法二：

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

Java 解法二：

```class Solution {
public String longestCommonPrefix(String[] strs) {
if (strs == null || strs.length == 0) return "";
for (int j = 0; j < strs[0].length(); ++j) {
for (int i = 0; i < strs.length; ++i) {
if (j >= strs[i].length() || strs[i].charAt(j) != strs[0].charAt(j)) {
return strs[i].substring(0, j);
}
}
}
return strs[0];
}
}```

C++ 解法三：

```class Solution {
public:
string longestCommonPrefix(vector& strs) {
if (strs.empty()) return "";
sort(strs.begin(), strs.end());
int i = 0, len = min(strs[0].size(), strs.back().size());
while (i < len && strs[0][i] == strs.back()[i]) ++i;
return strs[0].substr(0, i);
}
};```

Java 解法三：

```class Solution {
public String longestCommonPrefix(String[] strs) {
if (strs == null || strs.length == 0) return "";
Arrays.sort(strs);
int i = 0, len = Math.min(strs[0].length(), strs[strs.length - 1].length());
while (i < len && strs[0].charAt(i) == strs[strs.length - 1].charAt(i)) i++;
return strs[0].substring(0, i);
}
}```