Chaîne de concaténation de n chaînes en une seule chaîne

Question

Comment concaténer les chaînes n données pour créer une chaîne unique de sorte que, en combinant deux chaînes, le dernier caractère de la première chaîne soit le même que le premier caractère de la chaîne suivante.

Par exemple:

Entrée: AB2C, h23f2, c4dsh

Sortie: ab2cc4dshh23f2

J'ai essayé d'utiliser hashmap est-il une meilleure solution? Je ne peux pas être en mesure de traiter certains cas comme

Entrée: AB2C, h23fc, c555ab, c4dsh,

Sortie: ab2cc4dshh23fcc555ab

Dans l'exemple ci-dessus, il y a 2 possibilités pour la chaîne 2, mais prendre c555ab mènera à la fin de la chaîne. S'il y a beaucoup de possibilités à différents niveaux, comment les gérer pour obtenir les bonnes réponses?

Answer 1

En supposant que la fonction est appelée concat et prend un tableau de chaînes pool comme premier paramètre, et une chaîne accumulateur * s comme second paramètre:

Chaque fois que vous entrez dans la fonction concat, vous pouvez vérifier les points suivants règles:

1. Si pool est vide, puis retour s comme il est une réponse correcte.
2. Si s n'a pas une correspondance acceptable dans pool, retournez en arrière en retournant la valeur null ou un indicateur indiquant qu'il n'y a pas de réponse appropriée pour les entrées.
3. Recourir à chaque correspondance acceptable jusqu'à ce qu'il n'y ait plus de correspondance ou que la réponse soit correcte.

Cela conduira finalement à une réponse correcte, ou, à null ou à une autre valeur d'indicateur que les entrées n'avaient pas de réponse.

* Une chaîne d'accumulateurs est une chaîne qui accumule une valeur entre des appels de fonction récursifs. Dans ce cas, il commencerait comme une chaîne vide dans l'appel initial, puis à chaque appel de concat plus profondément dans la pile d'appels, il serait concaténé par sa correspondance de pool.

Voici une petite implémentation javascript, si vous l'exécutez, il produira un journal un peu bavarde:

function concat(pool, s) { 
 
\t s = s === undefined ? '' : s; 
 
\t if (pool.length === 0) { 
 
\t \t log("empty pool, s: " + s); 
 
\t \t return s; 
 
\t } 
 
\t for (let itr = 0; itr < pool.length; ++itr) { 
 
\t \t let v = pool[itr]; 
 
\t \t if (s.length === 0 || v.charAt(0) === s.charAt(s.length - 1)) { 
 
\t \t \t log(s + v + " is a candidate path, searching..."); 
 
\t \t \t let ret = concat(nSlice(pool, itr), s + v); 
 
\t \t \t if (ret !== null) { 
 
\t \t \t \t log("returning non-null ret: " + ret); 
 
\t \t \t \t return ret; 
 
\t \t \t } 
 
\t \t \t log(s + v + " hit a dead end, continuing..."); 
 
\t \t } else { 
 
\t \t \t log(s + v + " was not a candidate path, continuing..."); 
 
\t \t } 
 
\t } 
 
\t log("Returning null for given s: " + s); 
 
\t return null; 
 
} 
 

 
function nSlice(arr, index) { 
 
\t let a = arr.slice(0); 
 
\t a.splice(index, 1); 
 
\t return a; 
 
} 
 

 
function log(m) { 
 
    console.log(m); 
 
    let e = document.createElement('div'); 
 
    e.innerHTML = m; 
 
    document.body.appendChild(e); 
 
} 
 

 
[ 
 
\t ['ab2c', 'h23f2', 'c4dsh'], 
 
\t ['ab2c', 'h23fc', 'c555ab', 'c4dsh'], 
 
\t ['h23fc', 'c555ab', 'c4dsh', 'ab2c'] 
 
].forEach(v => { 
 
\t concat(v); 
 
\t log("------------------"); 
 
});