Найти минимальное число совпадений двух строк

Question

Алиса имеет две строки, начальную и цель. Она может удалить некоторое количество символов из начального, что даст ей подпоследовательность этой строки. Строка без удалений все еще считается подпоследовательностью. Учитывая эти две строки, можете ли вы найти минимальное количество подпоследовательностей начальных значений, которые при добавлении вместе образуют цель?

Функции MinimConcat () имеет два параметра:

initial: исходная строкачто вы получите подпоследовательности от цели: целевая строка, которую нужно сформировать

Формат ввода Для некоторых наших шаблонов мы обработали для вас синтаксический анализ. Если мы не предоставим вам функцию синтаксического анализа, вам нужно будет проанализировать входные данные напрямую. В этой задаче наш формат ввода выглядит следующим образом:

Первая строка - это исходная строка, из которой мы будем генерировать подпоследовательности. Вторая строка - это строка, которую нужно сформировать. Вот пример необработанного ввода:

abc bcbac

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

Если возможных решений нет, верните -1. Пример MinimConcat () Вход # 1

initial: "xyz"
goal: "xzyxz"

Выход: 3

function minimumConcat(initial, goal) {
     //Put your code here.
    return 0;
}

Answer 1

Вот, пожалуйста!

function minimumConcat(initial, goal) {
let result = 0;
let pattern = '';
let count1 = Array.apply(null, Array(26)).map(Number.prototype.valueOf, 0);
let count2 = Array.apply(null, Array(26)).map(Number.prototype.valueOf, 0);

initial.split('').forEach(c => {
    pattern = pattern + c
});
pattern = "^[" + pattern + "]*$";

if (!RegExp(pattern).test(goal)) return -1;

for (let i = 0; i < initial.length; i++) {
    count1[initial.charCodeAt(i) - 97]++;
}

for (let i = 0; i < goal.length; i++) {
    count2[goal.charCodeAt(i) - 97]++;
}

for (let i = 0; i < 26; i++) {
    result += Math.abs(count1[i] - count2[i]);
}

return result;
}

console.log(minimumConcat("abc", "bcbac"));

Answer 2

Цикл исходного массива строк для формирования массива строк цели.

function minimumConcat(initial, goal) {
    initial = initial.split('');
    goal = goal.split('');
    let res,count=0;
    while(true){
        if(goal.length > 0){
            res = checkChar(initial,goal);
            if(false === res){
                return -1;
            }
        }else{
            return count;
        }
        goal = res;
        count++;
    }
}
function checkChar(initial,goal){
    let started = false;
    let foundIndex = 0;
    for(let i=0; i<initial.length; i++){
        if(initial[i] == goal[foundIndex]){
            started = true;
            foundIndex++;
        }
    }
    if(started){
        return goal.slice(foundIndex);
    }else{
        return false;
    }
}
console.log(minimumConcat('abc','bcbac'));

Answer 3

Так как это выглядит как домашнее задание, я не буду сразу давать решение, вместо этого вот предложение о том, как его решить:

Я думаю, что самая сложная часть - это найти все подстроки, если выиспользуя Python, который упрощен на itertools, как упоминалось здесь .

Редактировать, я не заметил тег javascript, вы можете получить набор подстрок без библиотеки с парой for петель.

После получения всех комбинаций из initial вы можете отсортировать их, чтобы иметь самый длинный в первую очередь. А затем идите один за другим, удаляя их из goal. Подсчет каждый раз, когда вы удаляете. Если после перебора всех подстрок goal не является пустой строкой, то никакая подпоследовательность initial не может создать goal.