java - 如何为我的前缀匹配器算法找到更好的算法

Question

我正在解决在线问题，任务是这样的:

There are two arrays: numbers and prefixes.

• Array numbers contains numbers: “+432112345”, “+9990”, “+4450505”
• Array prefixes contains prefixes: “+4321”, “+43211”, “+7700”, “+4452”, “+4”

Find longest prefix for each number. If no prefix found for number, match with empty string.

For example:

• “+432112345” matches with the longest prefix “+43211” (not +4321, cause 43211 is longer).
• “+9990” doesn't match with anything, so empty string "".
• “+4450505” matches with “+4” (“+4452” doesn’t match because of the 2).

我想出了最直接的解决方案，我用每个前缀循环遍历每个数字。所以每次新号码时，我都会检查前缀，如果某个前缀比上一个长，我就会更改。

Map<String, String> numsAndPrefixes = new HashMap<>();

for (String number : A) {
    for (String prefix : B) {
        if (number.contains(prefix)) {
            // if map already contains this number, check for prefixes. 
            // if longer exists, switch longer one
            if (numsAndPrefixes.containsKey(number)) {
                int prefixLength = prefix.length();
                int currentLen = numsAndPrefixes.get(number).length();
                if (prefixLength > currentLen) {
                    numsAndPrefixes.put(number, prefix);
                }
            } else {
                numsAndPrefixes.put(number, prefix);
            }
        } else if (!number.contains(prefix) && !numsAndPrefixes.containsKey(number)){
            numsAndPrefixes.put(number, "");
        }
    }
}

所以它将有两个 for 循环。我发现每次我都一遍又一遍地做同样的工作，例如检查前缀。它有效，但速度很慢。问题是我想不出更好的办法。

有人可以解释一下他们将如何找到更好的算法吗？

更一般地说，如果您有一些可行的解决方案并试图找到更好的解决方案，您将如何继续？我还缺少哪些知识？

Answer 1

我会使用TreeSet来实现这个和 floor(E e)方法。

String[] numbers = { "+432112345", "+9990", "+4450505" };
String[] prefixes = { "+4321", "+43211", "+7700", "+4452", "+4" };

TreeSet<String> prefixSet = new TreeSet<>(Arrays.asList(prefixes));
for (String number : numbers) {
    String prefix = prefixSet.floor(number);
    while (prefix != null && ! number.startsWith(prefix))
        prefix = prefixSet.floor(prefix.substring(0, prefix.length() - 1));
    if (prefix == null)
        prefix = "";
    System.out.println(number + " -> " + prefix);
}

输出

+432112345 -> +43211
+9990 -> 
+4450505 -> +4