-1

I was looking for help on some pseudo code for my programming homework. The details are found here but to some it up: I receive strings from a file then I need to combine all of them into the shortest possible string. For example ABC AAB CAB could turn into AABCAB because the letters in the strings overlap. 

 ABC
AAB
   CAB
------
AABCAB

I have troubles understanding what logic I can use for this problem. I've thought of splitting the strings by their length-1 until I get a single character then look for that same character(s) in other strings but it wouldn't work that well.

4

1 回答 1

1

这是相当低效的，但这应该有效：

String findShortestOverlap(String total, ArrayList<String> stringsLeft)
{
    if(stringsLeft.size() == 0) return total;
    String shortest = "";
    boolean first = true;
    for(int i = 0 ; i < stringsLeft.size() ; i++)
    {
         //combine stringsLeft.get(i) with total and call it newTotal. That is find the biggest overlap between these 2 strings.
         newTotal = findShortestOverlap(newTotal, /*copy of stringsLeft with the ith string removed*/);
         if(first || newTotal.length() < shortest.length())
         {
             first=false;
             shortest=newTotal;
         }
    }
    return newTotal
{

我没有测试过这个。我还假设存在更有效的算法，但这是我的蛮力攻击。

找到 2 个字符串之间的最大重叠应该是一个简单的问题，这就是将问题分解为的原因。

对这个方法的第一次调用应该""是总数。

获得一些简单效率的最简单方法是在此函数之外保存一个“全局”变量，该变量包含迄今为止找到的“最短”字符串。然后仅newTotal = findShortestOverlap(...)在 newTotal 短于您迄今为止找到的最短字符串时才调用。这可以从树上剪掉很多分支，如果你在算法的早期找到了一个接近最优的解决方案，它应该很快就会从那里开始。

于 2013-10-15T18:06:09.137 回答