javascript - 将多个字符串打洞/组合成一个(可能最短的)字符串，其中包括每个字符串的所有字符

Question

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

所以，解释一下问题:

假设我的字符串很少

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

结果字符串应该是这样的:

"sjmachppoalidveonrk"

jack :sjmachppoalidveonrk

apple: sjmachppoalidveonrk

solid:sjmachppoalidveonrk

=====================================>>>> 全部向前

这些都是手动评估，示例中的输出可能不是 100% 完美。

所以，关键是每个字符串的所有字母都必须存在于输出中FORWARD DIRECTION(这里是实际问题所在)，并且可能服务器将发送最终的字符串和像 27594 这样的数字将生成并传递以提取 token ，在所需的结尾。如果我必须用尽可能少的字符串打洞它会容易得多(这种情况只有唯一的字符就足够了)。但是在这种情况下有几点:

1. 字母可以出现多次，但我必须重复使用任何字母字母如果可能，例如:对于 solid 和 hold o > l > d 可以重用为正向，但用于 apple (a > p) 和 spark(p > a) 我们必须重复 a，因为在一种情况下它出现在 p 之前对于 apple，在 p 之后对于 sparks 所以我们需要重复a 或 p。甚至，我们不能这样做 p > a > p 因为它不会涵盖这两种情况因为我们在 a 之后需要两个 p 用于 apple

2. 我们直接没有选择放置单个 p 并使用相同的一次提取索引两次，我们需要多个 p 没有选项留下作为输入字符串包含该

3. 我(不)确定，一组可能有多个输出字符串。但令人担忧的是它的长度应该是最小的，如果组合向前覆盖所有标记，则该组合无关紧要。最小可能长度的所有(或一个)输出需要追踪。
4. 将此点作为 EDIT 添加到此帖子中。在阅读评论并知道它已经存在之后问题被称为 shortest common supersequence problem我们可以定义结果字符串将是最短的我们可以从中重新生成任何输入字符串的字符串删除一些(0 到 N)个字符，这与所有输入都可以在结果字符串中的正向找到相同。

我尝试过，从一个任意字符串开始，然后分析下一​​个字符串并拆分所有字母，并相应地放置它们，但是经过一段时间后，似乎可以将当前字符串字母放在更好的位置方式，如果根据当前字符串放置最后一个字符串(或前一个字符串)的字母。但是，该字符串再次根据已处理的内容(多个)进行分析和放置，并且将某些内容放置在未处理的内容上似乎很困难，因为我们需要处理它。或者我是否可以维护所有已处理/未处理树的树将有助于构建最终字符串？有什么比它更好的方法，它似乎是一个蛮力？

注意:我知道还有很多其他的转换可能，请尽量不要建议使用其他任何东西，我们正在研究它。

Answer 1

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

此策略通过尝试找到将 2 个单词组合在一起的最佳方式来发挥作用。它被认为是最好的，因为它的字母最少。每个单词都被输入到一个不断增长的“合并”单词中。每次添加新词时，都会在现有词中搜索要合并的词中存在的匹配字符。一旦找到一个，就将它们分成两组并尝试加入(使用手头的规则，如果字母已经存在则不需要添加 2 等)。该策略通常会产生良好的效果。

join_word 方法需要两个你想加入的词，第一个参数被认为是你想加入另一个词的词。然后它搜索将 into 和 word 拆分为 2 个单独部分以合并在一起的最佳方法，它通过查找任何共享的公共(public)字符来做到这一点。这就是 splits_on_letter 方法的用武之地。

splits_on_letter 方法接受一个单词和一个您希望拆分的字母，然后返回一个二维数组，该数组包含该字符上所有可能的拆分左侧和右侧。例如 splits_on_letter('boom', 'o') 将返回 [["b","oom"],["bo","om"],["boo", "m"]]，这就是我们如何使用字母o作为分割点的所有组合。

---

开头的sort()是试图将相似的元素放在一起。合并元素的顺序通常会影响结果长度。我尝试的一种方法是根据他们(与他们的同龄人)使用的常用字母的数量对它们进行排序，但结果各不相同。然而，在我所有的测试中，我可能有 5 或 6 个不同的单词集可供测试，如果使用更大、更多样化的单词数组，您可能会发现不同的结果。

输出是

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