查找两个字符串的最小concat数量

Question

爱丽丝有两个字符串，首字母和目标。她可以从开头删除一些字符，这将为她提供该字符串的子序列。没有删除的字符串仍被视为其自身的子序列。给定这两个字符串，您能否找到初始的子序列的最小数目，将它们组合在一起即可形成目标？

功能minimumConcat（）有两个参数：

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

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

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

abcbcbac

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

如果没有可能的解决方案，则返回-1。示例minimumConcat（）输入＃1

initial: "xyz"
goal: "xzyxz"

输出：3

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

Answer 1

[我认为，最困难的部分是查找所有子字符串，如果您使用的是itertools所简化的Python，如here所述。

具有initial中的所有组合后，您可以对它们进行排序，使其具有最长的优先顺序。然后一步一步地将它们从goal中删除。每次删除时都在计数。如果在遍历所有子字符串之后，goal不是空字符串，则initial的任何子序列都不能构造goal。

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