Punch/Объединение нескольких строк в одну (кратчайшую) строку, которая включает в себя все символы каждой строки в прямом направлении

Ответ 1

Я придумал несколько грубый метод. Этот способ находит оптимальный способ объединить 2 слова, а затем сделать это для каждого элемента массива.

Эта стратегия работает, пытаясь найти наилучший способ объединить 2 слова вместе. Это считается лучшим, имея наименьшее количество букв. Каждое слово подается в постоянно растущее "слитое" слово. Каждый раз, когда добавляется новое слово, выполняется поиск существующего слова для совпадающего символа, который существует в слове, который должен быть объединен. Как только один найден, оба разделены на 2 набора и попытаются быть объединенными (используя правила под рукой, не нужно добавлять 2, если письмо уже существует ect..). Стратегия обычно дает хорошие результаты.

Метод join_word принимает 2 слова, которые вы хотите присоединиться, первым параметром считается слово, в которое вы хотите поместить другого. Затем он ищет лучший способ разделить into и word на две отдельные части, чтобы объединиться вместе, и делает это, ища любые общие общие символы. Здесь приходит метод splits_on_letter.

Метод splits_on_letter принимает слово и письмо, которое вы хотите разделить, затем возвращает 2d-массив всех возможных левых и правых частей разделения на этот символ. Например, 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;
}

Ответ 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;
}

В действии

Это может быть улучшено путем простого запуска верхнего кода с некоторыми вариантами массива (улучшение на 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;
}

В действии

Это довольно близко к минимальному числу символов ive оценено (возможно, в лучшем случае может быть минимизация на 244%)

Ive также написал функцию для получения минимального количества символов и один, чтобы проверить, не сработало ли какое-то слово, вы можете найти их здесь

Ответ 3

Я использовал идею Динамическое программирование, чтобы сначала создать кратчайшую строку в прямом направлении, как указано в OP. Затем я объединил результат, полученный на предыдущем шаге, чтобы отправить в качестве параметра вместе со следующей строкой в ​​списке. Ниже приведен рабочий код в java. Надеюсь, это поможет достичь оптимального решения, если мое решение будет определено как не оптимальное. Пожалуйста, не стесняйтесь сообщать о любых мешах для кода ниже:

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

Самая сложная временная сложность решения выше была бы O(product of length of all input strings), когда все строки имеют все символы различны, и даже ни один символ не совпадает между любой парой строк.

Ответ 4

Вот оптимальное решение, основанное на динамическом программировании в JavaScript, но оно может пройти только через solid на моем компьютере, пока не закончится память. Он отличается от решения @CodeHunter тем, что он сохраняет весь набор оптимальных решений после каждой добавленной строки, а не только из одного из них. Вы можете видеть, что число оптимальных решений растет экспоненциально; даже после solid уже имеется 518 640 оптимальных решений.

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