我正在解决在线问题,任务是这样的:
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 循环。我发现每次我都一遍又一遍地做同样的工作,例如检查前缀。它有效,但速度很慢。问题是我想不出更好的办法。
有人可以解释一下他们将如何找到更好的算法吗?
更一般地说,如果您有一些可行的解决方案并试图找到更好的解决方案,您将如何继续?我还缺少哪些知识?
最佳答案
我会使用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
关于java - 如何为我的前缀匹配器算法找到更好的算法,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/60249158/