6

假设我有以下字符串对象列表：

ABC1, ABC2, ABC_Whatever

从这个列表中提取最常见的字符的最有效方法是什么？所以我会得到ABC。

4

7 回答 7

6

StringUtils.getCommonPrefix(String... strs)来自 Apache Commons Lang。

于 2013-08-10T16:39:55.463 回答
0

这对你有用

 public static void main(String args[]) {
    String commonInFirstTwo=greatestCommon("ABC1","ABC2");
    String commonInLastTwo=greatestCommon("ABC2","ABC_Whatever");
    System.out.println(greatestCommon(commonInFirstTwo,commonInLastTwo));
}

public static String greatestCommon(String a, String b) {
    int minLength = Math.min(a.length(), b.length());
    for (int i = 0; i < minLength; i++) {
        if (a.charAt(i) != b.charAt(i)) {
            return a.substring(0, i);
        }
    }
    return a.substring(0, minLength);
}
于 2013-08-10T16:33:28.507 回答
0

您散列给定列表中单词的所有子字符串并跟踪这些子字符串。出现次数最多的那个就是您想要的那个。这是一个示例实现。它返回最常见的子字符串

static String mostCommon(List<String> list) {
    Map<String, Integer> word2Freq = new HashMap<String, Integer>();
    String maxFreqWord = null;
    int maxFreq = 0;
    for (String word : list) {
        for (int i = 0; i < word.length(); ++i) {
            String sub = word.substring(0, i + 1);
            Integer f = word2Freq.get(sub);
            if (f == null) {
                f = 0;
            }
            word2Freq.put(sub, f + 1);
            if (f + 1 > maxFreq) {
                if (maxFreqWord == null || maxFreqWord.length() < sub.length()) {
                    maxFreq = f + 1;
                    maxFreqWord = sub;
                }
            }
        }
    }

    return maxFreqWord;
}

如果您有多个公共子字符串，上述实现可能还不够。使用其中的地图。

System.out.println(mostCommon(Arrays.asList("ABC1", "ABC2", "ABC_Whatever")));
System.out.println(mostCommon(Arrays.asList("ABCDEFG1", "ABGG2", "ABC11_Whatever")));

退货

ABC
AB
于 2013-08-10T16:42:36.410 回答
0

您的问题只是寻找最长公共前缀的标准问题的改写

于 2013-08-10T16:55:06.600 回答
0

如果您知道常见字符是什么，那么您可以使用 .contains() 方法检查其他字符串是否包含这些字符。

于 2013-08-10T18:25:56.710 回答
0

如果您愿意使用第三方库，那么以下使用jOOλ会为您生成该前缀：

String prefix = Seq.of("ABC1", "ABC2", "ABC_Whatever").commonPrefix();

免责声明：我为 jOOλ 背后的公司工作

于 2016-04-15T11:24:13.593 回答
-1

如果有 N 个字符串并且其中的最小长度是 M 个租船人，那么在最坏的情况下（当所有字符串都相同时），最有效（正确）的答案将采用 N * M。

outer loop - each character of first string at a time
inner loop - each of the strings
test       - each charterer of the string in inner 
             loop against the charterer in outer loop.

如果我们不针对内部循环中的第一个字符串进行测试，则性能可以调整到 (N-1) * M

于 2013-08-10T16:43:28.023 回答