Задача: Общая подпоследовательность наибольшей длины

Условие: на вход подаются две строки, необходимо вывести их наидлиннейшую общую подпоследовательность, а точнее ее длину.

Подпоследовательность - совокупность символов, не обязательно смежных, идущих слева направо в том же порядке, что и в исходной строке.

Пример:

Ввод: text1 = "abcde", text2 = "ace" 

Вывод: 3

Объяснение: "ace"

Ввод: text1 = "abc", text2 = "def"

Вывод: 0

Решение :

Python

class Solution(object):
    def longestCommonSubsequence(self, text1, text2):
        m, n = len(text1), len(text2)
        
        # Create a 2D array to store the length of the longest common subsequence
        dp = [[0] * (n + 1) for _ in range(m + 1)]
        
        # Fill the dp array using bottom-up dynamic programming
        for i in range(1, m + 1):
            for j in range(1, n + 1):
                if text1[i - 1] == text2[j - 1]:
                    dp[i][j] = dp[i - 1][j - 1] + 1
                else:
                    dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])
        
        # The result is stored in the bottom-right cell of the dp array
        return dp[m][n]