14. 最长公共前缀
题目描述
编写一个函数来查找字符串数组中的最长公共前缀。
如果不存在公共前缀,返回空字符串 ""
。
示例 1:
输入:strs = ["flower","flow","flight"] 输出:"fl"
示例 2:
输入:strs = ["dog","racecar","car"] 输出:"" 解释:输入不存在公共前缀。
提示:
1 <= strs.length <= 200
0 <= strs[i].length <= 200
strs[i]
仅由小写英文字母组成
方法一:字符比较
我们以第一个字符串
遍历结束,说明所有字符串的前
时间复杂度
java
class Solution {
public String longestCommonPrefix(String[] strs) {
if (strs == null || strs.length == 0) return "";
String prefix = strs[0]; // 设定第一个字符串为初始公共前缀
for (int i = 1; i < strs.length; i++) {
// 如果当前字符串不是以 prefix 开头,就缩短 prefix
while (!strs[i].startsWith(prefix)) {
prefix = prefix.substring(0, prefix.length() - 1);
if (prefix.isEmpty()) return "";
}
}
return prefix;
}
}
cpp
class Solution {
public:
string longestCommonPrefix(vector<string>& strs) {
int n = strs.size();
for (int i = 0; i < strs[0].size(); ++i) {
for (int j = 1; j < n; ++j) {
if (strs[j].size() <= i || strs[j][i] != strs[0][i]) {
return strs[0].substr(0, i);
}
}
}
return strs[0];
}
};
ts
function longestCommonPrefix(strs: string[]): string {
const len = strs.reduce((r, s) => Math.min(r, s.length), Infinity);
for (let i = len; i > 0; i--) {
const target = strs[0].slice(0, i);
if (strs.every(s => s.slice(0, i) === target)) {
return target;
}
}
return '';
}
python
class Solution:
def longestCommonPrefix(self, strs: List[str]) -> str:
for i in range(len(strs[0])):
for s in strs[1:]:
if len(s) <= i or s[i] != strs[0][i]:
return s[:i]
return strs[0]