DP 정복 - 5.3 문자열 인터리빙 확인 문제

이번에는 문자열 인터리빙 문제를 풀어본다.

 

문자열 인터리빙 : 두 개의 문자열이 있을 때 모든 글자의 순서가 유지되면서 새로 만들어진 문자열을 의미.

예를 들어 'ABC', 'EFG'와 같이 두 개의 문자열이 있을 때, 'AEBFCG'는 인터리빙 된 문자열이 된다.

 

재귀 호출로 풀기 위한 조건들을 정리해보면

1. 인터리빙의 길이가 주어진 두 개의 문자열의 합과 같지 않으면 False 반환

2. 모든 문자열이 빈 문자열이면 True 반환

3. 아래의 경우에 해당되면 True 반환

 3-1. 첫 번째 문자열의 첫 글자와 인터리빙 문자열의 첫 글자가 같거나

 3-2. 두 번째 문자열의 첫 글자와 인터리빙 문자열의 첫 글자가 같으면

앞에서부터 한 글자씩 비교하면서 확인.

 

위의 내용을 소스로 옮기면 다음과 같다.

import sys

sys.setrecursionlimit(10 ** 5)


def solve(a, b, c):
    la, lb, lc = len(a), len(b), len(c)
    if la == 0 and lb == 0 and lc == 0:
        return True
    if la + lb != lc:
        return False

    case1, case2 = False, False

    if la != 0 and a[0] == c[0]:
        case1 = solve(a[1:], b, c[1:])

    if lb != 0 and b[0] == c[0]:
        case2 = solve(a, b[1:], c[1:])

    return case1 or case2


if __name__ == '__main__':
    a, b, c = input().split()
    print(solve(a, b, c))

시간 복잡도 가시 간 복잡도가 O(2^n) 이기 때문에 n이 늘어날수록 시간 복잡도가 늘어날 수밖에 없다.

때문에 DP로 구현을 하면 되는데..

 

이번에도 지난번과 같이 2차원 배열을 사용하고

첫 번째 열과 첫 번째 행을 미리 채운다. 채우는 조건은 다음과 같다.

0. (0, 0)의 값은 0이다. 빈 문자열일 경우를 의미.

1. 현재 문자가 인터리빙 문자와 같으면 바로 위쪽(행의 경우) 혹은 위쪽(열의 경우)과 같은 값으로 채운다.

2. 현재 문자가 인터리빙 문자와 다르면 False로 채운다.

 

그다음에 (1, 1)부터 (m, n)까지 채워 나간 다음에 (m, n)의 값을 리턴하면 된다.

구현은 생각보다 번거로워서 이번 건 패스!