Common Child - HackerRankの問題の解決方法

以下に、Pythonでの動的計画法を使用したコード例を示します。

def commonChild(s1, s2):
    m = len(s1)
    n = len(s2)
    dp = [[0] * (n + 1) for _ in range(m + 1)]
    for i in range(m):
        for j in range(n):
            if s1[i] == s2[j]:
                dp[i + 1][j + 1] = dp[i][j] + 1
            else:
                dp[i + 1][j + 1] = max(dp[i][j + 1], dp[i + 1][j])
    return dp[m][n]

このコードでは、2次元のdp配列を使用して共通の部分文字列の最長の長さを計算しています。文字列の各文字を比較し、一致する場合は左上のセルの値に1を加えます。一致しない場合は、左のセルと上のセルの中で最大の値を選択します。最終的な結果は、dp[m][n]に格納されています。

方法2: 再帰的な解法 動的計画法以外にも、再帰的な解法を使用してこの問題を解くこともできます。以下に、Pythonでの再帰的な解法のコード例を示します。

def commonChild(s1, s2):
    if len(s1) == 0 or len(s2) == 0:
        return 0
    elif s1[-1] == s2[-1]:
        return commonChild(s1[:-1], s2[:-1]) + 1
    else:
        return max(commonChild(s1[:-1], s2), commonChild(s1, s2[:-1]))

このコードでは、与えられた文字列の最後の文字を比較し、一致する場合はそれを含めた部分文字列の最長の長さを再帰的に求めます。一致しない場合は、片方の文字列を1文字短くした状態で再帰呼び出しを行います。最終的な結果は、再帰的な呼び出しの中での最大値となります。