Можно ли слить две строки в одну сохраняя порядок символов?

Рейтинг: 2Ответов: 1Опубликовано: 25.07.2023

Программа проверяет можно ли сформировать заданную строку S из двух других строк P1 и P2 так, чтобы не осталось лишних символов.

Символы в P1 и P2 должны быть в том же порядке, что и в S.

Пример:

radency можно сформировать с помощью rdnc и aey:

S  : r a d e n c y = radency
P_1: r   d   n c   = rdnc
P_2:   a   e     y = aey

Попытка решения:

const stringChecker = function (s, p1, p2) {
  let result = p1 + p2;
  const a = result.split('').sort().join('');
  const b = s.split('').sort().join('');
    
  return a === b;
};
javascript алгоритм
Источник: Stack Overflow на русском

Ответы

▲ 2

Решение за экспоненту - буквальное кодирование задачи:

const stringChecker = (s, p1, p2) => {
    const search = (i, j) => 
        (i + j === s.length) ||
        (p1[i] === s[i + j] && search(i + 1, j)) ||
        (p2[j] === s[i + j] && search(i, j + 1))
    ;
    return s.length === p1.length + p2.length && search(0, 0);
};

console.log(stringChecker('radency', 'rdnc', 'aey'));
console.log(stringChecker('radency', 'rdnd', 'aey'));

Решение за квадрат по времени и по памяти. Вопрос - можно ли быстрее?

const stringChecker = (s, p1, p2) => {
    const cache = [];
    const search = (i, j) => {
        if (cache[i] === undefined) {
            cache[i] = [];
        }
        if (cache[i][j] === undefined) {
            cache[i][j] = (
                (i + j === s.length) ||
                (p1[i] === s[i + j] && search(i + 1, j)) ||
                (p2[j] === s[i + j] && search(i, j + 1))
            );
        }
        return cache[i][j];
    };

    return s.length === p1.length + p2.length && search(0, 0);
};

console.log(stringChecker('radency', 'rdnc', 'aey'));
console.log(stringChecker('radency', 'rdnd', 'aey'));