Longest Common Subsequence

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

Даны два слова. Подпоследовательность — то, что остаётся от слова, если вычеркнуть часть букв и не менять порядок остальных. Нужно найти длину самой длинной подпоследовательности, общей для обоих слов. Наш пример: у «plum» и «lump» общая «lum», ответ 3.

1143 Longest Common SubsequenceРазбор · 1×

Пример: a = «plum», b = «lump». В обоих есть p, но на разных концах: смотрите, как последняя клетка её отбрасывает.

lumpplum
заполненоэтот шаг, сравниваемые буквыберём отсюдаответ и его буквы

dp[i][j]: длина наибольшей общей подпоследовательности первых i букв plum и первых j букв lump

01/39
сначала · назад · пуск · шаг
Скорость
1function lcs(a, b):
2 dp = table of len(a) + 1 by len(b) + 1
3 set row 0 and column 0 to 0 // an empty prefix
4 for i from 1 to len(a):
5 for j from 1 to len(b):
6 if a[i - 1] == b[j - 1]:
7 dp[i][j] = dp[i - 1][j - 1] + 1
8 else:
9 dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])
10 return dp[len(a)][len(b)]
состояние
dp
[[–, –, –, –, –], [–, –, –, –, –], [–, –, –, –, –], [–, –, –, –, –], [–, –, –, –, –]]
i
–
j
–
историянажмите шаг, чтобы вернуться

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

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

  1. Если последние буквы двух префиксов равны, какая-то наибольшая общая подпоследовательность кончается этой буквой: что бы ответ ни взял вместо неё, это можно заменить на неё. Значит, клетка — диагональ плюс один.
  2. Если они разные, хотя бы одна из двух букв не стоит в конце ответа, поэтому ответ — в клетке сверху или слева: большее из двух.
  3. Каждая клетка читает только клетки с префиксами короче, а они при обходе по строкам уже заполнены. Общая буква не на своём месте, как p здесь, к счёту ничего не добавляет.

Сложность

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

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

Решить на LeetCode ↗

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