2套字符串，找到一個字符串，可以從構造或者設置字符串

Question

鑑於以下幾組：

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; 
    } 

Answer 1

可以顯著縮小，你需要尋找，以檢查其中每組單詞可能開始的構造字符串置換的量。在這種情況下，唯一的兩種選擇是親愛的和de因爲de是的子串親愛的。一旦獲得字符串開始，您可以獲取較長字符串的子字符串，在這種情況下，"dear".substring("de".length())返回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); 
    } 
} 

你需要看出來的是，如果有多個匹配字符串，字符串或與您要查找的字符串開始的唯一的事。