Как найти лучший алгоритм для моего алгоритма сопоставления префиксов

Question

Я решал проблему в сети, и задача была примерно такой:

Существует два массива: числа и префиксы .

• Массив numbers содержит числа: «+432112345», «+9990», «+4450505»
• Массив prefixes содержит префиксы: «+4321», «+ 43211 »,« +7700 »,« +4452 »,« +4 »

Найти самый длинный префикс для каждого номера. Если префикс для номера не найден, сопоставьте его с пустой строкой.

Например:

• «+ 432112345» соответствует самому длинному префиксу «+43211» (не +4321, причина 43211 длиннее).
• «+ 9990» ни с чем не совпадает, поэтому пустая строка «».
• «+ 4450505» соответствует «+4» («+4452» не делает т совпадают из-за 2).

Я придумал самое простое решение, где я набрал oop через каждый номер с каждым префиксом. Поэтому каждый раз, когда я набираю новый номер, я проверяю префиксы. Если какой-то префикс будет длиннее предыдущего, я буду менять.

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

Answer 2

Необходимая структура данных: tr ie.

• Добавить все префиксы в tr ie
• Для каждой строки S в numbers:
  • Начать с root из tr ie
  • Для каждого символа в S:
    • Если есть ссылка с текущего узла, связанный с текущим символом, go по этой ссылке на следующий узел
    • Если ссылки нет, вы достигли самого длинного префикса - префикс, сохраненный в текущем узле, является ответом для S

Этот алгоритм работает в O(length(prefixes) + length(numbers))

Answer 3

Почему такие сложные логики c и структуры данных? Эта проблема аналогична задаче classi c по поиску максимального числа из списка чисел, и поэтому она имеет решение:

public class Main {
    public static void main(String[] args) {
        String[] numbers = { "+432112345", "+9990", "+4450505" };
        String[] prefixes = { "+4321", "+43211", "+7700", "+4452", "+4" };
        String max;
        for (String number : numbers) {
            max = "";
            for (String prefix : prefixes) {
                if (number.startsWith(prefix)) {
                    if (max.length() < prefix.length()) {
                        max = prefix;
                    }
                }
            }
            System.out.println(number + " matches with the longest prefix " + max);
        }
    }
}

Вывод:

+432112345 matches with the longest prefix +43211
+9990 matches with the longest prefix 
+4450505 matches with the longest prefix +4

Answer 4

Вы используете .contains(). Вы должны использовать .startsWith(). Это намного быстрее.

Затем в вашем else if вы проверяете то, что вы уже проверяли в if.

Это только один подход о том, как улучшить алгоритм:

Сортировка префиксов:

+ 43211 +4321 +4452 +4 + 7700

Что в этом хорошего? Ну, сначала он всегда найдет самый длинный префикс. Вы можете выйти из l oop и вам не нужно искать более длинные префиксы.

Arrays.sort(prefixes, new Comparator<String>() {
@Override
public int compare​(String o1, String o2) {
    return o1.startsWith(o2) ? 1 : o1.compareTo(o2);
}
});

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

for (String number: numbers) {
    numsAndPrefixes.put(number, "");
    for (String prefix: prefixes) {
        if (number.startsWith(prefix, 1)) {
            numsAndPrefixes.put(number, prefix);
            break;
        }
    }
}

Но если ваш номер начинается с +1 и префикса нет, он продолжит проверять все префиксы с помощью +2 +3 +4 ... которые явно не совпадают. (Выпуск 1)

Также, если ваш номер начинается с +9, префикс будет найден очень поздно. (Выпуск 2)

Как это исправить? Ну, вы можете сохранить индексы, где начинается +1, начинается +2, ...:

В нашем списке префиксов:

0      1     2     3  4  5   (index)
+1233  +123  +2233 +2 +3 +4

+ 2 начинается с индекса [2] и +3 начинается с индекса [4]. Поэтому, когда вы хотите узнать префикс для номера, начинающегося с +2, вам нужно только проверить элементы [2] и [3]. Это устранит проблемы 1 и 2.

Можно также сохранить индексы для большего количества цифр (например, где начинается +13).