97. Interleaving String

97. Interleaving String

 

https://youtu.be/3Rw3p9LrgvE?si=Bs1PKA3LI4l3H4my

 

class Solution:
    def isInterleave(self, s1: str, s2: str, s3: str) -> bool:

        # 길이 조건 확인
        if len(s1) + len(s2) != len(s3):
            return False

        dp = {}

        def dfs(i, j):
            # 종료 조건: s1과 s2를 모두 사용했을 때
            if i == len(s1) and j == len(s2):
                return True
            # 이미 계산된 경우 캐시된 값 반환
            if (i, j) in dp:
                return dp[(i, j)]

            # s1에서 문자를 가져오는 경우
            if i < len(s1) and s1[i] == s3[i + j] and dfs(i + 1, j):
                    return True

            # s2에서 문자를 가져오는 경우
            if j < len(s2) and s2[j] == s3[i + j] and dfs(i, j + 1):
                    return True

            # 위 조건을 만족하지 못하면 False
            dp[(i, j)] = False
            return False
        
        return dfs(0, 0)

 

동작 원리

1. DFS 호출:
   • 현재 인덱스 i와 j에서 s3[i+j]가 s1[i] 또는 s2[j]와 일치하는지 확인하고, 각각의 경우에 대해 재귀적으로 호출합니다.
2. 메모이제이션:
   • (i, j) 상태에서 결과를 dp에 저장하여 동일한 상태에 대한 중복 계산을 방지합니다.
3. 결과 반환:
   • dfs(0, 0) 호출로 탐색을 시작하며, 종료 조건을 만족하면 True를 반환합니다.

GPT

 

class Solution:
    def isInterleave(self, s1: str, s2: str, s3: str) -> bool:
        if len(s1) + len(s2) != len(s3):  # 문자열 길이가 맞지 않으면 False
            return False

        # DP 테이블 생성
        dp = [[False] * (len(s2) + 1) for _ in range(len(s1) + 1)]
        dp[0][0] = True  # 초기값: s1, s2, s3가 모두 빈 문자열인 경우

        # 첫 번째 문자열(s1)의 부분 문자열을 사용하는 경우
        for i in range(1, len(s1) + 1):
            dp[i][0] = dp[i - 1][0] and s1[i - 1] == s3[i - 1]

        # 두 번째 문자열(s2)의 부분 문자열을 사용하는 경우
        for j in range(1, len(s2) + 1):
            dp[0][j] = dp[0][j - 1] and s2[j - 1] == s3[j - 1]

        # DP 테이블 채우기
        for i in range(1, len(s1) + 1):
            for j in range(1, len(s2) + 1):
                dp[i][j] = (dp[i - 1][j] and s1[i - 1] == s3[i + j - 1]) or \
                           (dp[i][j - 1] and s2[j - 1] == s3[i + j - 1])

        return dp[len(s1)][len(s2)]  # 최종 결과

 

코드 설명

1. DP 테이블 정의:
   • dp[i][j]: s1의 첫 iii개 문자와 s2의 첫 jjj개 문자가 s3의 첫 i+ji + ji+j개 문자를 구성할 수 있는지 여부를 저장합니다.
2. 초기화:
   • dp[0][0] = True: 모든 문자열이 빈 문자열인 경우 가능합니다.
   • dp[i][0]: s1의 부분 문자열만으로 s3를 구성할 수 있는지 확인합니다.
   • dp[0][j]: s2의 부분 문자열만으로 s3를 구성할 수 있는지 확인합니다.
3. 점화식:
   • dp[i][j] = True는 다음 두 조건 중 하나가 참인 경우:
     • dp[i - 1][j]가 참이고, s1[i - 1] == s3[i + j - 1]
     • dp[i][j - 1]가 참이고, s2[j - 1] == s3[i + j - 1]
4. 결과 반환:
   • 최종적으로 dp[len(s1)][len(s2)]에 True가 저장되어 있으면, s3는 s1과 s2의 교차 문자열입니다.