Common Child

Problem Link
https://www.hackerrank.com/challenges/common-child/problem?isFullScreen=true

✅ Problem Summary

주어진 두 개의 문자열(s1, s2)를 비교하여 최장공통부분수열(LCS, Longest Common Subsequence)의 길이를 계산하는 문제

---

📑 My Answer

• 모든 테스트 케이스 통과

 def commonChild(s1, s2):
    lgth = len(s1)
    matrix = []

    # Make LCS matrix
    for i in range(lgth + 1):
        matrix.append([])
        for j in range(lgth + 1):
            if i == 0 or j == 0:
                matrix[i].append(0)
            elif s1[i - 1] == s2[j - 1]:
                matrix[i].append(matrix[i - 1][j - 1] + 1)
            elif s1[i - 1] != s2[j - 1]:
                matrix[i].append(max(matrix[i - 1][j], matrix[i][j - 1]))

    return matrix[lgth][lgth]

---

💼 Takeaway

• matrix[i - 1][j - 1] + 1의 의미 → 해당 문자가 제시된 두 문자열 모두 속해 있으므로, 이전 단계에서 만들었던 공통 부분 수열 집합에 문자를 새롭게 추가하는 것

• max(matrix[i - 1][j], matrix[i][j - 1])의 의미 → 현재 비교하는 상태 이전의 상황들 중 더 긴 공통부분수열을 갖고 있는 것을 선택하는 것

---