# 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:** strs = ["flower","flow","flight"]
**Output:** "fl"
``````

Example 2:

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

Constraints:

• `1 <= strs.length <= 200`
• `0 <= strs[i].length <= 200`
• `strs[i]` consists of only lowercase English letters.

C++ 解法一：

``````class Solution {
public:
string longestCommonPrefix(vector<string>& 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<string>& 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<string>& 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);
}
}
``````

Github 同步地址：

https://github.com/grandyang/leetcode/issues/14

https://leetcode.com/problems/longest-common-prefix

https://leetcode.com/problems/longest-common-prefix/discuss/6910/Java-code-with-13-lines

https://leetcode.com/problems/longest-common-prefix/discuss/6940/Java-We-Love-Clear-Code!

https://leetcode.com/problems/longest-common-prefix/discuss/6926/Accepted-c%2B%2B-6-lines-4ms

LeetCode All in One 题目讲解汇总(持续更新中…)

（欢迎加入博主的知识星球，博主将及时答疑解惑，并分享刷题经验与总结，快快加入吧～）

|

Venmo 打赏

—|—

 微信打赏 Venmo 打赏
（欢迎加入博主的知识星球，博主将及时答疑解惑，并分享刷题经验与总结，试运营期间前五十位可享受半价优惠～）

×

Help us with donation