找到两个字符串的最小连接数

Question

Alice 有两个字符串，初始和目标。她可以从初始值中删除一些字符，这将为她提供该字符串的子序列。没有删除的字符串仍被视为其自身的子序列。给定这两个字符串，你能找出初始的子序列的最小数量，当它们附加在一起时，将形成目标吗？函数 minimumConcat() 有两个参数：初始：您将从中获取子序列的源字符串目标：需要形成的目标字符串输入格式 对于我们的一些模板，我们已经为您处理了解析。如果我们没有为您提供解析功能，您将需要直接解析输入。在这个问题中，我们的输入格式如下：第一行是我们将从中生成子序列的初始字符串 第二行是要形成的目标字符串 这是原始输入的示例：美国广播公司预期输出返回可以附加在一起形成目标的初始的最小可能子序列的数量。如果没有可能的解决方案，则返回 -1。示例 minimumConcat() 输入 #1initial: "xyz"goal: "xzyxz"输出：3function minimumConcat(initial, goal) {     //Put your code here.    return 0;}

Answer 1

循环初始字符串数组以形成目标字符串数组。

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 2

干得好！

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 3

由于这看起来像作业，我不会立即给出解决方案，而是提供有关如何解决它的建议：

我认为最难的部分是找到所有子字符串，如果您使用的itertools是这里提到的简化的 Python 。

编辑，我没有注意到 javascript 标签，你可以得到子字符串集，没有库，有几个for循环。

获得所有组合后，initial您可以将它们排序为最长的。然后将它们从goal. 每次删除时都要计数。如果在遍历所有子字符串后，goal不是空字符串，则initial不能构造 的子序列goal。