строковый алгоритм домашнее задание / интервью как вопрос

Question

Допустим, нам нужны строки A и B. Задача состоит в том, чтобы вставить любые необходимые буквы в строку B, чтобы в итоге получить строку A.

Например:

A - This is just a simple test 
B - is t a sim te

Итак, если мы посмотрим на строку A следующим образом:

--is -- ---t a sim--- te--

или:

---- is ---t a sim--- te--

, то ясно, что мы можем построить строку A из строки B, ивывод должен быть в указанном выше письменном формате (оба ответа верны).

Можете ли вы придумать алгоритм, который решит это в разумные сроки?Довольно просто найти решение методом грубой силы, но мне нужно что-то более изощренное, чем это.

Answer 1

Вы можете взять Алгоритм расстояния Левенштейна в качестве основы и расширить его, чтобы также запомнить символы, которые были добавлены / удалены / заменены. Это будет работать за линейное время.

Answer 2

Вы можете просто найти первое вхождение символов B в A, просто начните искать вхождение после последнего найденного в A индекса, например, в вашем случае:

A - This is just a simple test 
B - is t a sim te

i: 3rd place in A,
s: 4th place in A,
' ': 5th place in A,
t: 12th place in A, (because last index was 4)
' ': ...
a: ....

Это O(|A|+|B|) и потому что |A| > |B| это O(|A|).

После нахождения индексов легко конвертировать B в A, просто добавив символы A между двумя индексами в B.

Редактировать: Такжеесли нет совпадения с этим алгоритмом, он работает нормально (в B будет несколько символов, которых нет в A из последнего индекса).

Answer 3

Я на самом деле думаю, что грубая сила будет самой быстрой, но вы должны изменить строку A, чтобы сделать это быстрее всего за один проход ... просто переберите A, измените каждую букву на "-", которая не соответствует букве, которую вы ищете ибо если это не космическая сделка ... это будет постоянное время и не требует дополнительного хранения ... в основном ваше время будет равно N. Конечно, вы должны иметь дело с токенами из "B", поэтому, как только вы найдете " i "вам нужно убедиться, что следующая буква" s ", чтобы вы нашли" is ", но она все еще должна быть быстрой, просто не возвращайтесь в позицию I, если следующая буква не s ... это должно направить вас в правильном направлении, не давая решения вашей домашней работы ...

Answer 4

Я думаю, что вы могли бы сделать это в линейном времени и пространстве, например так (псевдокод, полностью не проверен):

String f( String a, String b ) {
  String result;

  // Iterate over 'a' and 'b' in parallel. If both have the same
  // character, add it to the result. Otherwise, if 'a' has a space add a space to the result, otherwise add a dash.
  int idxB = 0;
  for (int idxA = 0; idxA < a.length(); ++idxA ) {
    if (a[idxA] == b[idxB]) {
      result.append(a[idxA]);
      ++idxB;
    } else if (a[idxA] == ' ') {
      result.append(' ');
    } else {
      result.append('-');
    }
  }

  // Tack on dashes to the result until it's as long as 'a'.
  while (result.length() < a.length()) {
    result.append('-');
  }

  return result;
}

Answer 5

Я думаю, вы могли бы определить, возможно ли это с помощью хорошего выражения reg.так как может быть или не быть 1 или более символов между любыми из предложенных в B.