Информация об изменениях

Сообщение Re[4]: Принудительный выход из рекурсии в случае, если ответ от 20.11.2020 15:27

Изменено 20.11.2020 15:37 Lazytech

Re[4]: Принудительный выход из рекурсии в случае, если ответ
Здравствуйте, Stanislav V. Zudin, Вы писали:

SVZ>На первый взгляд задача очень похожа на сортировку слиянием — два линейных прохода по двум массивам.

Сначала я примерно так и сделал, только вот это решение заваливало некоторые тестовые случаи. Проблема в том, что символы в part1 и part2 не всегда уникальны между part1 и part2 возможны «ложные перекрытия» (см. пример ниже).
  Еще один лог модифицированного решения 
s = Bananas from Bahamas
part1 = Bahas
part2 = Bananas from am
pos1, pos2, mergeConfirmed = 0 0 false
pos1, pos2, mergeConfirmed = 1 0 false
pos1, pos2, mergeConfirmed = 2 0 false
pos1, pos2, mergeConfirmed = 0 1 false
pos1, pos2, mergeConfirmed = 0 2 false
pos1, pos2, mergeConfirmed = 0 3 false
pos1, pos2, mergeConfirmed = 0 4 false
pos1, pos2, mergeConfirmed = 0 5 false
pos1, pos2, mergeConfirmed = 0 6 false
pos1, pos2, mergeConfirmed = 0 7 false
pos1, pos2, mergeConfirmed = 0 8 false
pos1, pos2, mergeConfirmed = 0 9 false
pos1, pos2, mergeConfirmed = 0 10 false
pos1, pos2, mergeConfirmed = 0 11 false
pos1, pos2, mergeConfirmed = 0 12 false
pos1, pos2, mergeConfirmed = 0 13 false
pos1, pos2, mergeConfirmed = 1 13 false
pos1, pos2, mergeConfirmed = 2 13 false
pos1, pos2, mergeConfirmed = 3 13 false
pos1, pos2, mergeConfirmed = 4 13 false
pos1, pos2, mergeConfirmed = 3 14 false
pos1, pos2, mergeConfirmed = 3 15 false
pos1, pos2, mergeConfirmed = 4 15 false
pos1, pos2, mergeConfirmed = 5 15 false
pos1, pos2, mergeConfirmed = 1 14 true
PREVENTIVE EXIT COULD BE HERE!
mergeConfirmed = true
Re[4]: Принудительный выход из рекурсии в случае, если ответ
Здравствуйте, Stanislav V. Zudin, Вы писали:

SVZ>На первый взгляд задача очень похожа на сортировку слиянием — два линейных прохода по двум массивам.

Сначала я примерно так и сделал, только вот это решение заваливало некоторые тестовые случаи. Проблема в том, что символы в part1 и part2 не всегда уникальны между part1 и part2 возможны «ложные перекрытия» (см. пример ниже).
  Еще один лог модифицированного решения 
s = Bananas from Bahamas
part1 = Bahas
part2 = Bananas from am
pos1, pos2, mergeConfirmed = 0 0 false
pos1, pos2, mergeConfirmed = 1 0 false
pos1, pos2, mergeConfirmed = 2 0 false
pos1, pos2, mergeConfirmed = 0 1 false
pos1, pos2, mergeConfirmed = 0 2 false
pos1, pos2, mergeConfirmed = 0 3 false
pos1, pos2, mergeConfirmed = 0 4 false
pos1, pos2, mergeConfirmed = 0 5 false
pos1, pos2, mergeConfirmed = 0 6 false
pos1, pos2, mergeConfirmed = 0 7 false
pos1, pos2, mergeConfirmed = 0 8 false
pos1, pos2, mergeConfirmed = 0 9 false
pos1, pos2, mergeConfirmed = 0 10 false
pos1, pos2, mergeConfirmed = 0 11 false
pos1, pos2, mergeConfirmed = 0 12 false
pos1, pos2, mergeConfirmed = 0 13 false
pos1, pos2, mergeConfirmed = 1 13 false
pos1, pos2, mergeConfirmed = 2 13 false
pos1, pos2, mergeConfirmed = 3 13 false
pos1, pos2, mergeConfirmed = 4 13 false
pos1, pos2, mergeConfirmed = 3 14 false
pos1, pos2, mergeConfirmed = 3 15 false
pos1, pos2, mergeConfirmed = 4 15 false
pos1, pos2, mergeConfirmed = 5 15 false
pos1, pos2, mergeConfirmed = 1 14 true
PREVENTIVE EXIT COULD BE HERE!
mergeConfirmed = true


P.S. Если я правильно понял, имелось в виду нечто вроде этого:
  Не вполне рабочее решение 
function isMerge(s, part1, part2) {
  if (s.length !== part1.length + part2.length) {
    return false;    
  }

  const len = s.length;
  let pos1 = 0,
      pos2 = 0;
      
  for (let i = 0; i < len; i++) {
      if (part1[pos1] === s[i]) {
      pos1++;
    } else if (part2[pos2] === s[i]) {
      pos2++
    } else {
      return false;
    }
  }
  
  return true;
}

Такое решение заваливает некоторые тесты по вышеуказанной причине.