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

Question

Alice 有两个字符串，初始和目标。她可以从初始值中删除一些字符，这将为她提供该字符串的子序列。没有删除的字符串仍被视为其自身的子序列。给定这两个字符串，你能找出初始的子序列的最小数量，当它们附加在一起时，将形成目标吗？

函数 minimumConcat() 有两个参数：

初始：您将从中获取子序列的源字符串目标：需要形成的目标字符串

输入格式 对于我们的一些模板，我们已经为您处理了解析。如果我们没有为您提供解析功能，您将需要直接解析输入。在这个问题中，我们的输入格式如下：

第一行是我们将从中生成子序列的初始字符串 第二行是要形成的目标字符串 这是原始输入的示例：

美国广播公司

预期输出返回可以附加在一起形成目标的初始的最小可能子序列的数量。

如果没有可能的解决方案，则返回 -1。示例 minimumConcat() 输入 #1

initial: "xyz"
goal: "xzyxz"

输出：3

function 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"));