Самая длинная общая подпоследовательность строк
Проблема:
Напишите функцию, которая принимает два массива строк в качестве входных данных и возвращает самую длинную непрерывную последовательность строк, которые встречаются в обоих.
Например, для следующих двух массивов:
a = [“/home”, “/register”, “/login”, “/user”, “/one”, “/two”] b = [“/home”, “/red”, “/login”, “/user”, “/one”, “/pink”]
Вы должны вернуть следующее:
[“/login”, “/user”, “/one”]
Подход:
Ключевой вывод приходит из вопроса: «Существует ли рекурсивная подструктура проблемы, которую мы можем использовать?» и «Можем ли мы кэшировать промежуточные результаты рекурсивных вызовов?»
- Рассмотрим местоположения
i
иj
в массивахa
иb
соответственно. Как найти самую длинную общую подпоследовательность массивов, начинающуюся сa[i]
иb[j]
? - если
a[i] == b[j]
, то длина оптимальной подпоследовательности равна единице плюс длина самой длинной общей подпоследовательности массивов, начиная сa[i+1]
иb[j+1]
. - В противном случае оптимальная подпоследовательность пуста.
- Мы можем использовать динамическое программирование для кэширования промежуточных вычислений рекурсивного вызова в хеш-таблице для последующего повторного использования.
Если у вас есть рекурсивная функция, самую длинную общую подпоследовательность можно найти, многократно вызывая ее для двух массивов:
Итеративная реализация с компактными циклами:
В чем сложность приведенной выше реализации? Мы вызываем функцию longest_recursive
для каждой (i, j)
пары индексов исходных массивов. Следовательно, сложность составляет не менее O(MN)
, где M
и N
— размеры двух массивов. Хотя мы делаем дальнейшие рекурсивные вызовы longest_recursive
для каждого (i, j)
, обратите внимание, что все эти вызовы, кроме одного, возвращаются немедленно, используя постоянный поиск в таблице, и, следовательно, общая сложность составляет O(MN)
.
Этот анализ сложности подчеркивает ограничения рекурсивной реализации (хотя ее довольно хорошо иметь и легко программировать). Вот несколько других:
- Сигнатура функции
longest_recursive
длинная и представляет собой головную боль при обслуживании. Более короткая сигнатура функции всегда предпочтительнее. unordered_map
не гарантирует поиск без коллизий, а в худшем случае поиск карты может выполняться не за постоянное время, что приводит к снижению производительности.- Ошибки времени выполнения в рекурсии (особенно превышение глубины стека/плохие базовые случаи) трудно отлаживать.
- Для этой проблемы достаточно одной итерационной функции, чтобы вычислить
max_count
и обновить таблицу, что делает рекурсивную реализацию немного длиннее.
Мы можем изменить метод longest()
выше и заменить рекурсивный вызов следующим образом:
Тестирование:
Эта задача демонстрирует использование метода ElementsAre
тестов Gunit.
Несколько простых тестов для пустых списков:
Простые тесты для идентичных массивов и для массивов без общих элементов
И, наконец, сложный пример в условии задачи: