给k个字符串,求出他们的最长公共前缀(LCP)
在 "ABCD" "ABEF" 和 "ACEF" 中, LCP 为 "A"
在 "ABCDEFG", "ABCEFG", "ABCEFA" 中, LCP 为 "ABC"
这道题可以很轻易的想到两个思路.
下面是第二种思路的实现代码.
public String longestCommonPrefix(String[] strs) {
// 输入为空
if (strs.length == 0) {
return "";
}
//取最短的字符串为遍历字符串
for (int i = 1; i < strs.length; i++) {
if (strs[0].length() > strs[i].length()) {
String tmp = strs[0];
strs[0] = strs[i];
strs[i] = tmp;
}
}
//如果最短的字符串为空,返回空
if (strs[0].length() == 0) {
return "";
}
int j = 0;
for (; j < strs[0].length(); j++) {
if (!isAllSame(strs, j)) {
break;
}
}
return strs[0].substring(0, j);
}
/**
* 判断所有字符串在index位置的字符串是否相同
*/
private boolean isAllSame(String[] strs, int index) {
char c = strs[0].charAt(index);
for (String str : strs) {
if (str.charAt(index) != c) {
return false;
}
}
return true;
}
实现代码中,可以选择不做”排序”,随便拿一个字符串当做遍历的标杆都可以.但是需要遍历检查字符串不为空.
上述思路是取到最短的字符串,一来可以减少遍历次数,二来可以方便的进行判空.
2018-12-09 完成
以上皆为个人所思所得,如有错误欢迎评论区指正。
欢迎转载,烦请署名并保留原文链接。
联系邮箱:huyanshi2580@gmail.com