Java String-Collection：最长的公共前缀

Question

我收到了String（目录路径）的集合。 如何获得所有字符串的最长公共前缀？

实施例： [ “E：/用户/测试”， “E：/用户/测试/ ABC /”， “C：/方案”， “E：/数据”， “/测试”]

该解决方案必须比： [ “E：/”， “C：/程序”， “/测试”]

我不知道如何实现这...

感谢你的帮助， 问候

Answer 1

既不漂亮也不快，但似乎工作：

public List<String> longestCommonPrefixes(Collection<String> c) { 
    List<String> list = new ArrayList<>(c); 
    List<String> result = new ArrayList<>(); 
    while (!list.isEmpty()) { 
     String lcp = longestCommonPrefix(list); 
     result.add(lcp); 
     for (Iterator<String> it = list.iterator(); it.hasNext();) { 
      if (it.next().startsWith(lcp)) { 
       it.remove(); 
      } 
     } 
    } 
    return result; 
} 

private String longestCommonPrefix(List<String> list) { 
    Map<Character, Integer> map = new HashMap<>(); 
    for (String s : list) { 
     char c = s.charAt(0); 
     if (map.containsKey(c)) { 
      map.put(c, map.get(c) + 1); 
     } else { 
      map.put(c, 1); 
     } 
    } 
    char c = 0; 
    int max = 0; 
    for (Map.Entry<Character, Integer> e : map.entrySet()) { 
     int n = e.getValue(); 
     if (n > max) { 
      max = n; 
      c = e.getKey(); 
     } else if (n == max) { 
      c = 0; 
     } 
    } 
    if (c == 0) { 
     int maxLen = 0; 
     String sMaxLen = null; 
     for (String s : list) { 
      if (s.length() > maxLen) { 
       maxLen = s.length(); 
       sMaxLen = s; 
      } else if (s.length() == maxLen) { 
       sMaxLen = null; 
      } 
     } 
     return sMaxLen; 
    } else { 
     String s = null; 
     for (int i = 0; i < list.size(); i++) { 
      if (list.get(i).charAt(0) == c) { 
       s = list.get(i); 
       for (int j = i + 1; j < list.size(); j++) { 
        String s2 = list.get(j); 
        if (s2.charAt(0) != c) { 
         continue; 
        } 
        if (s.length() > s2.length()) { 
         s = s.substring(0, s2.length()); 
        } 
        for (int k = 0; k < s.length(); k++) { 
         if (s.charAt(k) != s2.charAt(k)) { 
          s = s.substring(0, k); 
          break; 
         } 
        } 
       } 
       break; 
      } 
     } 
     return s; 
    } 
}