Почему это работает
- Последняя буква сплетения 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].
- Таблица держит все пути сразу. Взять первую a из a кажется нормальным, но (1, 1) — false: дальше c нужна буква c, а её не предлагает ни одна строка. Другой выбор, (0, 1), доходит до конца.
- Каждая клетка читает только клетку сверху и клетку слева, а при обходе по строкам они уже заполнены, поэтому правая нижняя клетка отвечает за строки целиком.
Сложность
Время O(n × m) для a и b длины n и m: по клетке на каждую пару префиксов, каждая проверяется за константу. Память O(n × m) на таблицу; хватит одной строки, обновляемой на месте, O(m).
дальшеТеперь реши её сам, без подсказок.
Решить на LeetCode ↗