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

你需要看出来的是，如果有多个匹配字符串，字符串或与您要查找的字符串开始的唯一的事。