Проверьте, можно ли сформировать строки в списке путем объединения элементов в одном списке

Question

Проверьте, можно ли сформировать строки в списке путем объединения элементов в одном списке

Например:

Список ввода -

{ best,  rockstar,   star,  guide,  bestguide, rock }

Вывод: -

rockstar -> rock, star

bestguide -> best, guide

Здесь «рок-звезда» может быть сформирована из камня и звезды. Точно так же «bestguide» можно сформировать, соединив «best» и «guide».

Решение, которое у меня есть, - создать все комбинации строк, соединив друг друга (2 строки вместе, 3 строки вместе и т. Д. ) и сохраните на карте.

структура карты может выглядеть следующим образом:

Map<String, List<String>>

{rockstar : [rock, star], ....}

Теперь проверьте только обход исходного списка и отметьте карту. Если он найден, то это одно из возможных решений.

В поисках лучшего решения с лучшей сложностью времени / пространства

Answer 1

Я думаю, что одним из стандартных подходов, вероятно, было бы создание дерева из словаря. Затем для каждого кандидата пройдитесь по дереву и, когда соответствующий путь достигнет конца (помечая меньшее слово), продолжите снова с вершины дерева с оставшимся суффиксом кандидата. Нам может потребоваться несколько испытаний на каждого кандидата, если существуют похожие совпадения;но в словаре из 10000, если только данные не вырождены, в среднем их должно быть немного.

Answer 2

Во-первых, извините за мой плохой английский. У меня есть наивный способ, вы должны попробовать это:

шаг 1: сортировка списка в порядке убывания длин элементов

шаг 2: по очереди (слева направо от отсортированного списка)добавьте элементы один за другим в дерево по следующим правилам:

• Каждый узел дерева содержит строку, в корне дерева ничего нет

• Строка в каждом родительском узле содержит строки в своих дочерних узлах.

• шаг 3: получение результатов: если длина строки в узле равна сумме длин строк в дочерних узлах, то мы получаем желаемый результат.

Answer 3

Спасибо, что поделились этим забавным упражнением.

Используя Java 8+ и Streams, это лучший подход для итерации списка и обработки небольших или больших наборов данных.

Имейте в виду, что вы можете использовать метод:

• inputList.stream () списка для создания списка
• inputList.parallelStream () , если ваш список не содержит синхронизированный объект и не вызывает синхронизированный метод (который не допускает параллелизм).

Вот хороший пост на DZone, чтобы понять производительность Stream API https://dzone.com/articles/java-performance-for-looping-vs-streaming

            final String input = "best,rockstar,star,guide,bestguide,rock,fake,rockfaller";

        // Start to finding input pairs
        List<String> inputList = Arrays.asList(input.split(","));
        List<String> combi = inputList.stream()
                .filter(s -> input.contains(s) && input.lastIndexOf(s) != input.indexOf(s))
                .collect(Collectors.toList());

        // Build ouput
        final HashMap<String, List<String>> output = new HashMap<>();
        inputList.stream()
                // Remove pair words 
                .filter(s -> !combi.contains(s)) 
                .filter(s -> combi.stream().anyMatch(pair -> s.startsWith(pair) || s.endsWith(pair)) )
                .forEach( s -> {
                    List<String> result = combi.stream()
                            .filter(pair -> s.startsWith(pair) || s.endsWith(pair))
                            // Sort the output result
                            .sorted((s1, s2) ->  s.startsWith(s1) ? 0 : 1)
                            .collect(Collectors.toList());
                    Collections.sort(result);

                    if(result.size() > 1)
                    {
                        output.put(s, result);
                    }
                });

        System.out.println(output);

И это вывод, когда вы печатаете результат HashMap

{bestguide = [best, guide], rockstar = [rock, star]}

Answer 4

Это проблема с подмножеством сумм. Стандартным решением является динамическое программирование, но обычно вы найдете решения для целых чисел: Алгоритм суммы подмножеств

Адаптированный здесь это даст что-то вроде:

static List<String> substrings(String s) {
    List<String> l = new ArrayList<String>();
    for(int end=1; end < s.length()+1; ++end) {
        for(int start=0; start < end; ++start) {
            l.add(s.substring(start, end));
        }
    }
    return l;
}

static boolean isInConcatenations(String target, List<String> list) {
    Set<String> set = new HashSet<String>();
    List<String> ss = substrings(target);
    set.add("");
    for (String s: list) {
        if (s == target) continue; // do not use directly 'target' if it's in the list
        Set<String> prev = Set.copyOf(set);
        for (String sub: ss) {
            if ((sub.startsWith(s) && prev.contains(sub.substring(s.length(), sub.length()))) ||
                (sub.endsWith(s) && prev.contains(sub.substring(0, sub.length()-s.length()))) ) {
                set.add(sub);
            }
        }
    }
    return set.contains(target);
}

Здесь substrings(s) возвращает List всех непустых подстрок строки.

Сложность примерно равна length(list) * length(target)**2

Answer 5

1. Используйте автоматизацию AC и добавьте в нее все строки в наборе.

2. Сопоставьте все строки в наборе с точкой автоматизации и сопоставления записей.

3. Использование динамического программирования для объединения совпадающих точек.

Сложность времени в худшем случае: O (n * (сумма длин))

n исходит из нескольких вариантов длины, которые будут определены в процессе DP. Представьте себе набор строк {a, aa, aaa, aaaa, ..., a ^ n}.

Узнайте об автоматизации AC здесь: link

Answer 6

Вот подход грубой силы. Сначала мы можем сформировать список исходных терминов, а затем дважды повторить этот список, чтобы сгенерировать все возможности комбинирования. Для каждой комбинации, которая также уже содержится в исходном списке, мы печатаем эту комбинацию на консоли.

String[] terms = new String[] { "best",  "rockstar",   "star",  "guide",  "bestguide", "rock" };
List<String> list = Arrays.asList(terms);
Set<String> set = new HashSet<String>(list);
for (int i=0; i < list.size()-1; ++i) {
    for (int j=i+1; j < list.size(); ++j) {
        if (set.contains(list.get(i) + list.get(j))) {
            System.out.println(list.get(i) + list.get(j) + " -> " + list.get(i) + ", " + list.get(j));
        }
        if (set.contains(list.get(j) + list.get(i))) {
            System.out.println(list.get(j) + list.get(i) + " -> " + list.get(j) + ", " + list.get(i));
        }
    }
}

Это печатает:

bestguide -> best, guide
rockstar -> rock, star