打孔/将多个string合并为一个（最短的）string，其中包含每个string的所有字符

我的目的是将多个string打成一个单一的（最短的）string，该string将包含每个string的正向的所有字符。 这个问题不是特定于任何语言，而是更多地涉及algorithm部分。 （可能会在节点服务器中实现它，所以标记nodejs/javascript ）。

所以，要解释这个问题：

让我们考虑一下我有几个string

 ["jack", "apple", "maven", "hold", "solid", "mark", "moon", "poor", "spark", "live"] 

结果string应该是这样的：

 "sjmachppoalidveonrk" 

jack：s j m ac hppoalidveonr k

apple：sjm a ch pp oa l idv e onrk

固体：jmachpp o 盖子 veonrk

==================================== >>>>全部在前进的方向

这些都是人工评估，在这个例子中输出可能不是100％完美。

所以，重点是每个string的所有字母都必须存在于FORWARD DIRECTION的输出中（这里是实际的问题所在），并且服务器可能会发送最终的string，并且会生成27594这样的27594并将其传递以提取令牌，在要求的最后。 如果我不得不用最小的string来打出它，那么会更容易（这种情况下只有唯一的字符就足够了）。 但在这种情况下，有一些要点：

1. 字母可以多次出现，尽pipe我必须重用任何字母（如果可能的话），例如：for solid和hold o > l > d可以作为前向重用，但对于apple （ a > p ）和spark （ p > a ）我们不得不重复a就像在p之前出现apple ，在p之后出现sparks所以要么重复a ，要么重复a 。 我们不能做p > a > p ，因为它将涵盖两种情况，因为我们需要两个p

2. 我们没有select放置一个单一的p并在提取时使用相同的索引两次，我们需要多个p ，没有选项剩下的input令牌包含

3. 我（不确定），有一组string可能有多个输出。 但是关心的是它的长度应该是最小的，这个组合并不重要，如果它覆盖所有的令牌在前进的方向。 所有（或一个）可能长度最短的输出都需要跟踪。
4. 添加这一点作为编辑到这个职位。 在阅读了这些注释之后，我们知道已经存在的一个已知问题是最短公共超序列问题，我们可以定义结果string是最短的string，我们可以通过简单地删除一些（0到N）字符，这是相同的，因为所有的input可以在结果string中的正向中find。

我试着用一个任意string开始，然后对下一个string进行分析并分割所有的字母，并相应地放置它们，但是有些时候，似乎当前的string可以放在更好的位置，If最后一个string（或之前的string）字母是根据当前string放置的。 但是这个string再一次被分析，并且根据（多个）被处理的东西进行分析和放置，并且对某些没有被处理的东西进行处理似乎很困难，因为我们需要处理这些东西。 或者可能我维护所有已处理/未处理的树的树会有所帮助，build设最后的string？ 任何比它更好的方式，这似乎是一个蛮力！

注意 ：我知道还有很多其他的转换可能，请尽量不要提出任何其他的使用，我们正在做一些研究，任何问题的背景下将受到高度赞赏。 如果有什么不清楚或需要进一步的解释可以随意评论。 感谢大家耐心地阅读整个问题。

Answer 1

我想出了一个有点蛮力的方法。 这种方式find组合2个单词的最佳方式，然后为数组中的每个元素。

这种策略通过尝试find将两个单词组合在一起的最佳方式起作用。 通过使用最less的字母被认为是最好的。 每个单词都被input到一个不断增长的“合并”单词中。 每次添加一个新单词时，都会search现有单词，以find要合并的单词中存在的匹配字符。 一旦发现一个被分成两组，并试图join（使用手头的规则，如果信件已经存在等，不需要添加2）。 该策略通常会产生良好的结果。

join_word方法需要2个单词你想join，第一个参数被认为是你join_word字。 然后search最好的方法分裂into两个单独的部分合并在一起，它通过查找任何共享的通用字符。 这是splits_on_letter方法的来源。

splits_on_letter方法需要一个单词和一个你想要分割的字母，然后返回在该字符上分割所有可能左右两边的二维数组。 例如splits_on_letter('boom', 'o')会返回[["b","oom"],["bo","om"],["boo","m"]] ，这是所有我们如何使用字母o作为分割点的组合。

---

sort()在开头就是试图把元素放在一起。 合并元素的顺序通常影响结果长度。 我尝试的一种方法是根据他们使用的常用字母（与他们的同龄人）进行sorting，但结果是不同的。 然而，在我所有的testing中，我可能会用5或6个不同的单词集进行testing，可能会出现更大，更多不同的单词数组，您可能会发现不同的结果。

输出是

 spmjhooarckpplivden 

 var words = ["jack", "apple", "maven", "hold", "solid", "mark", "moon", "poor", "spark", "live"]; var result = minify_words(words); document.write(result); function minify_words(words) { // Theres a good sorting method somewhere which can place this in an optimal order for combining them, // hoever after quite a few attempts i couldnt get better than just a regular sort... so just use that words = words.sort(); /* Joins 2 words together ensuring each word has all its letters in the result left to right */ function join_word(into, word) { var best = null; // straight brute force each word down. Try to run a split on each letter and for(var i=0;i<word.length;i++) { var letter = word[i]; // split our 2 words into 2 segments on that pivot letter var intoPartsArr = splits_on_letter(into, letter); var wordPartsArr = splits_on_letter(word, letter); for(var p1=0;p1<intoPartsArr.length;p1++) { for(var p2=0;p2<wordPartsArr.length;p2++) { var intoParts = intoPartsArr[p1], wordParts = wordPartsArr[p2]; // merge left and right and push them together var result = add_letters(intoParts[0], wordParts[0]) + add_letters(intoParts[1], wordParts[1]); if(!best || result.length <= best.length) { best = result; } } } } // its possible that there is no best, just tack the words together at that point return best || (into + word); } /* Splits a word at the index of the provided letter */ function splits_on_letter(word, letter) { var ix, result = [], offset = 0;; while((ix = word.indexOf(letter, offset)) !== -1) { result.push([word.substring(0, ix), word.substring(ix, word.length)]); offset = ix+1; } result.push([word.substring(0, offset), word.substring(offset, word.length)]); return result; } /* Adds letters to the word given our set of rules. Adds them starting left to right, will only add if the letter isnt found */ function add_letters(word, addl) { var rIx = 0; for (var i = 0; i < addl.length; i++) { var foundIndex = word.indexOf(addl[i], rIx); if (foundIndex == -1) { word = word.substring(0, rIx) + addl[i] + word.substring(rIx, word.length); rIx += addl[i].length; } else { rIx = foundIndex + addl[i].length; } } return word; } // For each of our words, merge them together var joinedWords = words[0]; for (var i = 1; i < words.length; i++) { joinedWords = join_word(joinedWords, words[i]); } return joinedWords; } 

Answer 2

第一次尝试，没有真正优化（缩短183％）：

 function getShort(arr){ var perfect=""; //iterate the array arr.forEach(function(string){ //iterate over the characters in the array string.split("").reduce(function(pos,char){ var n=perfect.indexOf(char,pos+1);//check if theres already a possible char if(n<0){ //if its not existing, simply add it behind the current perfect=perfect.substr(0,pos+1)+char+perfect.substr(pos+1); return pos+1; } return n;//continue with that char },-1); }) return perfect; } 

在行动

---

这可以通过简单地运行上面的代码来改进一些arrays（200％的改进）：

 var s=["jack",...]; var perfect=null; for(var i=0;i<s.length;i++){ //shift s.push(s.shift()); var result=getShort(s); if(!perfect || result.length<perfect.length) perfect=result; } 

在行动

这非常接近估计的最小字符数 （在最好的情况下可能有244％的最小化）

我也写了一个函数来获取最less的字符数量和一个来检查某个单词是否失败，你可以在这里find它们

Answer 3

我已经使用dynamic规划的思想，首先产生OP中所述的最短可能的string。 然后，我将上一步获得的结果与列表中的下一个string一起作为参数发送。 下面是java的工作代码。 希望这将有助于达到最佳的解决scheme，以防万一我的解决scheme被认定为非最佳。 请随时举报以下代码的任何反案：

 public String shortestPossibleString(String a, String b){ int[][] dp = new int[a.length()+1][b.length()+1]; //form the dynamic table consisting of //length of shortest substring till that points for(int i=0;i<=a.length();i++){ for(int j=0;j<=b.length();j++){ if(i == 0) dp[i][j] = j; else if(j == 0) dp[i][j] = i; else if(a.charAt(i-1) == b.charAt(j-1)) dp[i][j] = 1+dp[i-1][j-1]; else dp[i][j] = 1+Math.min(dp[i-1][j],dp[i][j-1]); } } //Backtrack from here to find the shortest substring char[] sQ = new char[dp[a.length()][b.length()]]; int s = dp[a.length()][b.length()]-1; int i=a.length(), j=b.length(); while(i!=0 && j!=0){ // If current character in a and b are same, then // current character is part of shortest supersequence if(a.charAt(i-1) == b.charAt(j-1)){ sQ[s] = a.charAt(i-1); i--; j--; s--; } else { // If current character in a and b are different if(dp[i-1][j] > dp[i][j-1]){ sQ[s] = b.charAt(j-1); j--; s--; } else{ sQ[s] = a.charAt(i-1); i--; s--; } } } // If b reaches its end, put remaining characters // of a in the result string while(i!=0){ sQ[s] = a.charAt(i-1); i--; s--; } // If a reaches its end, put remaining characters // of b in the result string while(j!=0){ sQ[s] = b.charAt(j-1); j--; s--; } return String.valueOf(sQ); } public void getCombinedString(String... values){ String sSQ = shortestPossibleString(values[0],values[1]); for(int i=2;i<values.length;i++){ sSQ = shortestPossibleString(values[i],sSQ); } System.out.println(sSQ); } 

驱动程序：

 e.getCombinedString("jack", "apple", "maven", "hold", "solid", "mark", "moon", "poor", "spark", "live"); 

输出：

jmapphsolivecparkonidr

上述解决scheme的最坏情况时间复杂度为O(product of length of all input strings)当所有string都具有不同的字符时，即使任何一对string之间没有单个字符匹配。

Answer 4

这是一个基于JavaScript的dynamic编程的最佳解决scheme，但它只能在内存耗尽之前，在计算机上实现。 它不同于@ CodeHunter的解决scheme，因为它在每个添加的string之后保留整套最佳解决scheme，而不仅仅是其中之一。 你可以看到最优解的数量呈指数增长， 即使在solid之后，已经有518,640个最佳解决scheme。

 const STRINGS = ["jack", "apple", "maven", "hold", "solid", "mark", "moon", "poor", "spark", "live"] function map(set, f) { const result = new Set for (const o of set) result.add(f(o)) return result } function addAll(set, other) { for (const o of other) set.add(o) return set } function shortest(set) { //set is assumed non-empty let minLength let minMatching for (const s of set) { if (!minLength || s.length < minLength) { minLength = s.length minMatching = new Set([s]) } else if (s.length === minLength) minMatching.add(s) } return minMatching } class ZipCache { constructor() { this.cache = new Map } get(str1, str2) { const cached1 = this.cache.get(str1) if (!cached1) return undefined return cached1.get(str2) } set(str1, str2, zipped) { let cached1 = this.cache.get(str1) if (!cached1) { cached1 = new Map this.cache.set(str1, cached1) } cached1.set(str2, zipped) } } const zipCache = new ZipCache function zip(str1, str2) { const cached = zipCache.get(str1, str2) if (cached) return cached if (!str1) { //str1 is empty, so only choice is str2 const result = new Set([str2]) zipCache.set(str1, str2, result) return result } if (!str2) { //str2 is empty, so only choice is str1 const result = new Set([str1]) zipCache.set(str1, str2, result) return result } //Both strings start with same letter //so optimal solution must start with this letter if (str1[0] === str2[0]) { const zipped = zip(str1.substring(1), str2.substring(1)) const result = map(zipped, s => str1[0] + s) zipCache.set(str1, str2, result) return result } //Either do str1[0] + zip(str1[1:], str2) //or str2[0] + zip(str1, str2[1:]) const zip1 = zip(str1.substring(1), str2) const zip2 = zip(str1, str2.substring(1)) const test1 = map(zip1, s => str1[0] + s) const test2 = map(zip2, s => str2[0] + s) const result = shortest(addAll(test1, test2)) zipCache.set(str1, str2, result) return result } let cumulative = new Set(['']) for (const string of STRINGS) { console.log(string) const newCumulative = new Set for (const test of cumulative) { addAll(newCumulative, zip(test, string)) } cumulative = shortest(newCumulative) console.log(cumulative.size) } console.log(cumulative) //never reached