题目:
/**
*编写一个函数来查找字符串数组中的最长公共前缀。
*如果不存在公共前缀,返回空字符串 ""。
*/
难度:
简单
思路分析:
排序得到最短字符串后使用最短字符串和集合的值来比较
代码:
执行用时:2 ms, 在所有 Java 提交中击败了19.79%的用户
内存消耗:39.7 MB, 在所有 Java 提交中击败了15.45%的用户
public String longestCommonPrefix(String[] strs) {
//先将字符串转set(去重、排序)
TreeSet<String> set = new TreeSet<>(new Comparator<String>(){
@Override
public int compare(String o1, String o2) {
if(o1.length() < o2.length()){
return -1;
}else if(o1.length() > o2.length()){
return 1;
}else{
if(o1.equals(o2)){
return 0;
}else{
return 1;
}
}
}
});
set.addAll(Arrays.asList(strs));
//只有一个元素时直接返回结果
if(set.size() == 1){
return set.first();
}
String k = set.first();
String result = "";
for(int i = 0;i < k.length();i++){
//比较结果时只从最短字符串开始比较,如果比较的结果不等于false则最短字符串去掉最后一位继续比较
String z = k.substring(0,k.length()-i);
if(hasStartWith(z,set)){
result = z;
break;
}
}
return result;
}
public boolean hasStartWith(String str, Set<String> set){
for(String x : set){
if(!x.startsWith(str)){
return false;
}
}
return true;
}