leetcode第十四题 最长公共前缀

题目:

/**
 *编写一个函数来查找字符串数组中的最长公共前缀。
 *如果不存在公共前缀，返回空字符串 ""。
 */

难度:

简单

思路分析:

排序得到最短字符串后使用最短字符串和集合的值来比较

代码:

执行用时：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;
    }