我的目的是将多个字符串打造成一个(最短)字符串，该字符串将包含每个字符串向前方向的所有字符。这个问题不是特定于任何语言的，而是更多地进入algorithm部分(可能会在节点服务器中实现它，因此标记nodejs/javascript)。
所以，要解释这个问题：
让我们考虑我有几个字符串
["jack", "apple", "maven", "hold", "solid", "mark", "moon", "poor", "spark", "live"]
结果字符串应如下所示：
"sjmachppoalidveonrk"
杰克：SJMACHPPOALIDVEONRK
苹果： SJMACHPPOALIDVEONRK
固体：SJMachhppoalidveonrk
======================================================================>>>>=
=====================================================================这些都是手动评估，在示例中输出可能不是 100% 完美。
因此，关键是每个字符串的所有字母都必须存在于输出中FORWARD DIRECTION(这里实际问题属于)，服务器可能会发送最终的字符串和数字，例如27594将生成并传递以提取令牌，在所需的末端。如果我必须在尽可能小的字符串中打孔，它会容易得多(在这种情况下，只有唯一的字符就足够了)。但在这种情况下，有几点：
字母可以多次出现，尽管我必须重复使用任何 如果可能的话，字母，例如：对于
solid和holdo > l > d可以是 重新用作前进方向，但用于apple(a > p)和spark(p > a) 我们必须重复a，因为在一个情况下它出现在p对于apple，在p之后 对于sparks所以我们需要重复a或p.甚至，我们不能做p > a > p因为它不会涵盖这两种情况因为我们需要a后的两个p才能apple我们直接无法选择放置单个
p并使用相同的 在提取时间内索引两次，我们需要多个p而没有选择 左作为输入字符串包含- 我(不)确定，一组 字符串。但问题是它的长度应该是最小的， 如果它向前覆盖所有代币，则组合无关紧要。所有(或一个)尽可能小长度的输出 需要追踪。
- 将这一点作为编辑添加到这篇文章中。阅读评论并知道它已经是现有的 问题被称为我们能做的最短的常见超序列问题 定义生成的字符串将是尽可能短的字符串 我们可以简单地从中重新生成任何输入字符串的字符串删除一些(0 到 N)字符，这与可以在结果字符串中向前方向找到所有输入相同。
我尝试过，从任意字符串开始，然后分析下一个字符串并拆分所有字母，并相应地放置它们，但是经过一段时间，似乎可以以更好的方式放置当前的字符串字母，如果最后一个字符串(或前一个字符串)的字母是根据当前字符串放置的。但是，该字符串再次根据已处理的内容(多个)进行分析和放置，并且将某些内容置于未处理的内容中似乎很困难，因为我们需要处理它。或者我维护所有已处理/未处理树的树会有所帮助，构建最终字符串？还有比它更好的方法吗，它似乎是蛮力？
注意：我知道还有很多其他可能的转换，请尽量不要建议使用任何其他内容，我们正在对此进行一些研究。
我想出了一个有点蛮力的方法。这种方式找到了组合 2 个单词的最佳方法，然后针对数组中的每个元素进行操作。
这种策略通过尝试找到将 2 个单词组合在一起的最佳方法来起作用。通过拥有最少的字母，它被认为是最好的。每个单词都被输入到一个不断增长的"合并"单词中。每次添加新单词时，都会搜索现有单词以查找要合并的单词中存在的匹配字符。一旦找到一个，两个都分成 2 组并尝试连接(使用手头的规则，如果字母已经存在，则不需要添加 2 个......该策略通常会产生良好的结果。
join_word方法采用您希望加入的 2 个单词，第一个参数被视为您希望将另一个放入的单词。然后，它会搜索将into拆分并word分成 2 个独立部分合并在一起的最佳方法，它通过查找任何共享的公共字符来做到这一点。这就是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;
}第一次尝试，没有真正优化(缩短了 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;
}
在行动中
这非常接近我估计的最小字符数(在最好的情况下，244%的最小化可能是可能的)
Ive还编写了一个函数来获取最少数量的字符和一个检查某个单词是否失败的函数，您可以在此处找到它们
我使用了动态编程的思想，首先在 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)。
这是一个基于 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