2017-02-21 13 views
0

Учитывая следующие наборы строк:С 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; 
    } 
+0

Прежде чем спросить здесь, попробуйте хотя бы код. Мы не будем писать вашу программу для вас, если это то, о чем вы просите нас. –

+0

Я написал реализацию для грубой силы, принимая каждую возможную комбинацию обоих наборов и сравнивая их, что реально реально для небольших множеств. Я не могу понять, как это сделать. – intact28

+0

Работает ли он так, как ожидалось? Что с этим не так? –

ответ

0

Вы можете значительно сузить количество перестановок, которые вы должны проверить, находя, какие слова из каждого набора, возможно, начать сконструированный String. В этом случае единственными двумя вариантами являются дорогой и de, поскольку de является подстрокой дорогой. После запуска String вы можете взять подстроку более длинной строки, в этом случае "dear".substring("de".length()) возвращает ar, в котором говорится, что следующий элемент с правой стороны должен начинаться с ar. Поэтому в основном у вас есть два случая:

String stringLeft = "", stringRight = ""; 

if(stringLeft.length() == stringRight.length()) 
{ 
    //find two matching Strings here (one is substring of another) 
    String[] matching = getMatching(); //returns 1d array of size 2(if only two strings match) 
    stringLeft += matching[0]; 
    stringRight += matching[1]; 
} 
else 
{ 
    if(stringLeft.length() > stringRight.length()) 
    { 
     String start = stringLeft.substring(stringRight.length()); 
     //find string on right that starts with start 
     stringRight += getStringStartingWith(start); 
    } 
    else 
    { 
     String start = stringRight.substring(stringLeft.length()); 
     //find string on left that starts with start 
     stringLeft += getStringStartingWith(start); 
    } 
} 

Единственное, что вам нужно обратить внимание, если есть несколько совпадающих строк или строки, начинающиеся с подстроки, которую вы ищете.