Строка конкатенации n строк в одну строку

Question

Как объединить данные n строк, чтобы создать одну строку, такую, что при объединении двух строк последний символ первой строки должен быть таким же, как первый символ следующей строки.

Например:

Вход: ab2c, h23f2, c4dsh

Выход: ab2cc4dshh23f2

Я попытался с помощью HashMap есть ли лучшее решение? Я не могу быть в состоянии обрабатывать некоторые случаи, как

Вход: ab2c, h23fc, c555ab, c4dsh,

Выход: ab2cc4dshh23fcc555ab

В приведенном выше примере есть 2 возможности для 2-ой строки, но взятие c555ab приведет к концу строки. Если на разных уровнях есть много возможностей, как обращаться с ними, чтобы получить правильные ответы?

Answer 1

Предполагая, что функция называется concat и принимает массив строк pool в качестве первого параметра, и аккумулятор * строка s в качестве второго параметра:

Каждый раз, когда вы вводите функцию concat, вы можете проверить следующее правила:

1. Если pool пусто, то возвращают s как это правильный ответ.
2. Если s не имеет приемлемого соответствия в pool, то возвращается назад, возвращая нулевой или некоторый индикатор, что нет подходящего ответа для входов.
3. Рассчитывайте каждое подходящее совпадение до тех пор, пока: нет совпадений слева или правильный ответ найден.

Это, в конечном счете, приведет либо к правильному ответу, либо к нулевому или некоторому другому значению индикатора, что входы не получили ответа.

* Аккумуляторная строка - это та, которая накапливает значение между вызовами рекурсивных функций. В этом случае он будет начинаться как пустая строка в начальном вызове, а затем при каждом вызове concat глубже в стек вызовов он будет конкатенирован по его совпадению с pool.

Вот небольшой Javascript реализация, если вы запустите его он будет производить несколько подробного журнал:

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