В этой статье блога мы углубимся в проблему поиска длины самой длинной общей подпоследовательности между двумя строками, также известную как проблема «Общего дочернего элемента» на HackerRank. Мы рассмотрим несколько методов решения этой проблемы, приведя примеры кода для каждого подхода. Давайте начнем!

Метод 1: динамическое программирование с использованием двумерного массива

def commonChild(s1, s2):
    m, n = len(s1), len(s2)
    dp = [[0] * (n + 1) for _ in range(m + 1)]

    for i in range(1, m + 1):
        for j in range(1, n + 1):
            if s1[i - 1] == s2[j - 1]:
                dp[i][j] = dp[i - 1][j - 1] + 1
            else:
                dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])

    return dp[m][n]

Метод 2: динамическое программирование с использованием одномерного массива

def commonChild(s1, s2):
    m, n = len(s1), len(s2)
    dp = [0] * (n + 1)

    for i in range(1, m + 1):
        prev = 0
        for j in range(1, n + 1):
            curr = dp[j]
            if s1[i - 1] == s2[j - 1]:
                dp[j] = prev + 1
            else:
                dp[j] = max(dp[j], dp[j - 1])
            prev = curr

    return dp[n]

Метод 3: рекурсивный подход

def commonChild(s1, s2):
    if len(s1) == 0 or len(s2) == 0:
        return 0

    if s1[0] == s2[0]:
        return 1 + commonChild(s1[1:], s2[1:])

    return max(commonChild(s1[1:], s2), commonChild(s1, s2[1:]))

Метод 4: запоминание с помощью рекурсивного подхода

def commonChild(s1, s2):
    memo = {}

    def helper(s1, s2):
        if len(s1) == 0 or len(s2) == 0:
            return 0

        if (s1, s2) in memo:
            return memo[(s1, s2)]

        if s1[0] == s2[0]:
            memo[(s1, s2)] = 1 + helper(s1[1:], s2[1:])
        else:
            memo[(s1, s2)] = max(helper(s1[1:], s2), helper(s1, s2[1:]))

        return memo[(s1, s2)]

    return helper(s1, s2)

В этой статье мы рассмотрели несколько методов решения проблемы Common Child на HackerRank. Мы обсудили решения динамического программирования с использованием как 2D, так и 1D массивов, рекурсивного подхода и метода мемоизации для оптимизации рекурсивного решения. Каждый метод имеет свои преимущества и сложности, поэтому выбор правильного подхода зависит от конкретных требований вашей проблемы.

Реализуя эти методы, вы можете эффективно найти длину самой длинной общей подпоследовательности между двумя строками. Я надеюсь, что эта статья предоставила вам ценную информацию о решении проблемы Common Child на HackerRank.