[Hackerrank] [Medium] Common Child

https://www.hackerrank.com/challenges/common-child/problem

Common Child | HackerRank

풀이

• 입력으로 두 개의 string이 주어졌을 때 공통된 child의 최대 길이를 구하는 문제
  • child : string에서 문자를 1개 이상 삭제한 결과물
  • ex) s1 = ABCD, s2 = ABDC -> longest common child : ABC or ABD
  • ex) s1 = HARRY, s2 = SALLY -> longest common child : AY
• Dynamic programming으로 풀었음.
• python3 컴파일러로 제출했을 때 timeout발생했지만 Pypy3 컴파일러로 제출했을 때 error없이 완료됨.
• 2차원 matrix를 만든 뒤, m[ i ] [ j ] = s1[ : i ], s2 [ : j ] 까지 봤을 때의 longest common child의 길이로 정의
• 구현 편의 상 문자열 길이를 각각 1씩 추가해 matrix index를 1부터 시작.

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

    for i in range(s1_len+1):
        for j in range(s2_len+1):
            # index가 0인 부분은 건너뜀
            if i == 0 or  j == 0:
                continue
            # string이 같을 때, 이전 index까지의 longest common child(m[i-1][j-1])에다 1을 더해줌.
            elif s1[i-1] == s2[j-1]:
                m[i][j] =  m[i-1][j-1] + 1
            else:
                m[i][j] = max(m[i-1][j], m[i][j-1])

    return m[-1][-1]