Interleaving String

Средняя№97две строки

Даны три строки a, b и c. Нужно понять, можно ли сплести c из a и b: каждая буква обеих строк взята ровно один раз, порядок букв внутри каждой строки сохранён, а буквы a и b перемешаны как угодно. Наш пример: «acab» из «ab» и «ac» — true: a и c из «ac», потом a и b из «ab».

97 Interleaving StringРазбор · 1×

Пример: a = «ab», b = «ac», c = «acab». И a, и b начинаются с a, поэтому первая буква c может прийти из любой; подходит только один выбор.

acabc0a1c2a3b
true: можно построитьfalse: нельзяэтот шаг, его буквыберём отсюдасплетение за ответом

2 + 2 = 4 = len(c): длины сходятся, каждая буква a и b должна пойти в дело ровно один раз

01/24
сначала · назад · пуск · шаг
Скорость
1function isInterleave(a, b, c):
2 if len(a) + len(b) != len(c): return false
3 dp = table of len(a) + 1 by len(b) + 1, all false
4 dp[0][0] = true
5 for i from 0 to len(a):
6 for j from 0 to len(b):
7 if i > 0 and dp[i - 1][j]
8 and a[i - 1] == c[i + j - 1]:
9 dp[i][j] = true // the last letter from a
10 if j > 0 and dp[i][j - 1]
11 and b[j - 1] == c[i + j - 1]:
12 dp[i][j] = true // the last letter from b
13 return dp[len(a)][len(b)]
состояние
dp
–
i
–
j
–
историянажмите шаг, чтобы вернуться

← → шаг · пробел — пауза

Почему это работает

  1. Последняя буква сплетения i букв a и j букв b — это a[i - 1] или b[j - 1]. Значит, (i, j) можно построить, ровно когда можно построить (i - 1, j) и a[i - 1] — та самая буква c, или (i, j - 1) и b[j - 1].
  2. Таблица держит все пути сразу. Взять первую a из a кажется нормальным, но (1, 1) — false: дальше c нужна буква c, а её не предлагает ни одна строка. Другой выбор, (0, 1), доходит до конца.
  3. Каждая клетка читает только клетку сверху и клетку слева, а при обходе по строкам они уже заполнены, поэтому правая нижняя клетка отвечает за строки целиком.

Сложность

Время O(n × m) для a и b длины n и m: по клетке на каждую пару префиксов, каждая проверяется за константу. Память O(n × m) на таблицу; хватит одной строки, обновляемой на месте, O(m).

дальшеТеперь реши её сам, без подсказок.

Решить на LeetCode ↗

Задача и её условие принадлежат LeetCode. Здесь — наш пересказ, наш пример и наше решение. Patterns Hero не связан с LeetCode.