Решение задачи

Алгоритм решения задачи:

Это классическая задача на самую длинную общую подстроку, которую можно использовать с помощью динамического программирования. Пусть dp[i][j] — самый длинный общий суффикс между num1[0..i-1] и num2[0..j-1].

Поскольку наш dp получает доступ только к предыдущему состоянию dp и текущему состоянию dp, мы можем использовать 2 переменные dp, prevDP, которые оптимизируют пространство до O(N).

• Временная сложность: O(M*N), где M <= 1000 - максимум, N <= 1000 - минимум между соответствующей длиной nums1 и длиной nums2.
• Пространственная сложность: O(N)