Учитывая следующие наборы строк:С 2 набора строк, найти строку, которые могут быть построены либо из установленных
are yo
you u
how nhoware
alan arala
dear de
Мне нужно найти последовательность, которая может быть построена путем конкатенации строк в любом columnm , и он должен использовать одинаковое количество элементов в обоих случаях.
Например, «dearalanhowareyou» может быть сконструирован из обоих наборов строк, каждый раз используя 5 элементов.
Указан недопустимый выбор будет «dearalanhoware», так как он будет использовать 4 элемента из левой колонки, но только 3 из права
Проблема взята отсюда:
https://open.kattis.com/problems/correspondence
Я использую этот сайт для улучшения будущих собеседований, и я просто не могу понять, что это вообще.
Моя единственная работающая реализация - это подход грубой силы, который использует все возможные комбинации каждого набора, что не очень хорошее решение из-за сложности времени.
Мой код прямо сейчас:
list1 = getPermutations("",send1);
list2 = getPermutations("",send2);
ArrayList<String> duplicateValues = new ArrayList<String>();
for (int i = 0; i < list1.size(); i++) {
if (list2.contains(list1.get(i))) {
duplicateValues.add(list1.get(i));
}
private static ArrayList<String> getPermutations(String currentResult, ArrayList<String> possibleChars) {
ArrayList<String> result = new ArrayList<>(possibleChars.size());
for (String append : possibleChars) {
String permutation = currentResult + append;
result.add(permutation);
if (possibleChars.size() > 0) {
ArrayList<String> possibleCharsUpdated = (ArrayList) possibleChars.clone();
possibleCharsUpdated.remove(new String(append));
result.addAll(getPermutations(permutation, possibleCharsUpdated));
}
}
return result;
}
Прежде чем спросить здесь, попробуйте хотя бы код. Мы не будем писать вашу программу для вас, если это то, о чем вы просите нас. –
Я написал реализацию для грубой силы, принимая каждую возможную комбинацию обоих наборов и сравнивая их, что реально реально для небольших множеств. Я не могу понять, как это сделать. – intact28
Работает ли он так, как ожидалось? Что с этим не так? –