给k个字符串,求出他们的最长公共前缀(LCP)

原创
2017/06/14 02:09
阅读数 12

public class Solution {
    /**
     * @param s: The first string
     * @param b: The second string
     * @return true or false
     */
    public String longestCommonPrefix(String[] strs) {
        // write your code here
        if(strs.length == 0 || strs == null) return "";
        Map<String,Integer> map = new HashMap<String,Integer>();
        List<String> list = new ArrayList<String>();
        for(int i=0;i<strs.length;i++){
            List<String> alist = new ArrayList<String>();
            if(strs[i] == null || strs[i].equals("")) return "";
            alist.addAll(text(strs[i]));
            for(int j=0;j<alist.size();j++) {
                String b = alist.get(j);
                if(!map.containsKey(b)) {
                    map.put(b, 1);
                } else {
                    int id=map.get(b);
                    id++;
                    map.put(b, id);
                }
            }
        }
        Set<String> sss = map.keySet();
        list.addAll(sss);
        List<String> alist = new ArrayList<String>();
        for(int i=0;i<list.size();i++){
            if(map.containsKey(list.get(i)) && map.get(list.get(i))==strs.length) {
                alist.add(list.get(i));
            }
        }
        int flag=0;
        for(int i=0;i<alist.size() && flag==0;i++) {
            flag=1;
            for(int j=i+1;j<alist.size();j++) {
                int a = alist.get(i).length();
                int b = alist.get(j).length();
                if (a>b) {
                    flag=0;
                    String c = alist.get(i);
                    alist.set(i, alist.get(j));
                    alist.set(j, c);
                }
            }
        }
        return alist.get(alist.size()-1);
    }
    
    public Set<String> text(String s) {
        Set<String> set = new HashSet<String>();
        for(int i=s.length();i>0;i--) {
            set.add(s.substring(0,i));
        }
        return set;
    }
}

展开阅读全文
打赏
0
0 收藏
分享
加载中
更多评论
打赏
0 评论
0 收藏
0
分享
返回顶部
顶部