我采用的方法为相对比较暴力的,但是也是较容易理解得,废话少说上代码:
class Solution {
public String longestCommonPrefix(String[] strs) {
if (strs.length == 0) {
return "";
}
// 最长前缀末尾位置
int end = strs[0].length() - 1;
for (int i = 1; i < strs.length; ++i) {
int j = 0;
// 优化1: 不用比较整个字符串, 只要比较前缀长度即可
for (; j <= end && j < strs[i].length(); ++j) {
if (strs[0].charAt(j) != strs[i].charAt(j)) {
break;
}
}
// j 的位置不相同
end = Math.min(end, j - 1);
// 没有公共前缀, 不用再遍历剩余字符串
if (end < 0) break;
}
return strs[0].substring(0, end + 1);
}
}
因为我们在传入多个字符串进行判定的时候,从前往后比较过程中,最长公共前缀肯定是越来越短的,所以我们把第一个子串作为对比子串,其他的为比较子串。