LeetCode 97(Interleaving String, Python)

1. 문제 링크

• Interleaving String - LeetCode

LeetCode - The World's Leading Online Programming Learning Platform

2. 문제 설명

• 두 개의 문자열이 주어질 때, 두 문자열이 교차로 섞여서 주어진 문자열 목표 문자열을 형성할 수 있는지 판단하여 True, False를 반환하는 문제
• 예시) s1 = "aabcc", s2 = "dbbca", s3 = "aadbbcbcac”가 주어지면 s1, s2를 적당히 잘라 교차로하면 aa/dbbc/bc/a/c 가 되어 s3를 만들 수 있으므로 True

3. 처음 풀이

• 한 덩어리 씩 말고 그냥 두 문자열 s1, s2에서 한 글자 씩 가져와서 s3를 만들 수 있는 지 보면 된다.
• s1의 첫 글자만 s3 첫 글자와 같으면 s1, s3의 첫 글자를 빼고 나머지에 대해 재귀
• s2의 첫 글자만 s3 첫 글자와 같으면 s2, s3의 첫 글자를 빼고 나머지에 대해 재귀
• s1, s2의 첫 글자가 같은 경우 s3 첫 글자와 다르면 False, 같으면 s1, s3의 첫 글자 빼고 재귀와 s2, s3의 첫 글자 빼고 재귀 두 가지를 실행
• s1, s2의 첫 글자 중 s3의 첫 글자와 같은게 없으면 False
• 종결 조건: s1, s2를 첫 글자를 하나 씩 제거하다보면 둘 중 하나가 먼저 바닥이 난다. 이때 남아있는 문자열이 남은 s3와 같아야 한다. 이를 통해 True, False 반환
• 이렇게만 하면 Time Limit Error가 뜬다. 따라서 True, False 반환 직전 이 결과를 딕셔너리에 저장해두고 처음 따질 때 이 딕셔너리에 저장된 결과인 지 확인해보기.

class Solution:
    def isInterleave(self, s1: str, s2: str, s3: str) -> bool:
        hist = {}  # 성공적인 계산 결과 저장하는 딕셔너리
        hist_no = {}  # 실패한 계산 결과 저장하는 딕셔너리

        def helper(s1, s2, s3):
            if len(s1) + len(s2) > len(s3):
                return False
            if len(s1) + len(s2) < len(s3):
                return False

            # 이전에 처리된 부분 문자열인지 확인
            if (s1, s2) in hist:
                if hist[(s1, s2)] == s3:
                    return True
            if (s2, s1) in hist:
                if hist[(s2, s1)] == s3:
                    return True
            if (s1, s2) in hist_no:
                if hist_no[(s1, s2)] == s3:
                    return False
            if (s2, s1) in hist_no:
                if hist_no[(s2, s1)] == s3:
                    return False

            # 끝 부분 도달하여 하나의 문자열이 바닥난 경우
            if s1 == '':
                # s1이 비어있을 때, s2와 s3가 일치하는지 확인
                if s2 == s3:
                    hist[(s1, s2)] = s3
                    hist[(s2, s1)] = s3
                    return True
                else:
                    hist_no[(s1, s2)] = s3
                    hist_no[(s2, s1)] = s3
                    return False
            if s2 == '':
                # s2가 비어있을 때, s1과 s3가 일치하는지 확인
                if s1 == s3:
                    hist[(s1, s2)] = s3
                    hist[(s2, s1)] = s3
                    return True
                else:
                    hist_no[(s1, s2)] = s3
                    hist_no[(s2, s1)] = s3
                    return False

            # 부분 문자열이 교차로 섞이는지 확인
            if s1[0] == s2[0]:
                # s1과 s2의 첫 번째 문자가 같을 때
                if s1[0] != s3[0]:
                    # s1과 s2의 첫 번째 문자가 s3의 첫 번째 문자와 같지 않으면 실패
                    hist_no[(s1, s2)] = s3
                    hist_no[(s2, s1)] = s3
                    return False
                else:
                    # s1의 첫 번째 문자를 넣는 경우와 s2의 첫 번째 문자를 넣는 경우 
                    # 두 가지 경우를 확인하며 재귀적으로 진행
                    result = helper(s1[1:], s2, s3[1:]) or helper(s1, s2[1:], s3[1:])
                    if result:
                        # 성공적으로 교차로 섞인 경우, 결과를 저장
                        hist[(s1, s2)] = s3
                        hist[(s2, s1)] = s3
                    else:
                        # 실패한 경우도 저장
                        hist_no[(s1, s2)] = s3
                        hist_no[(s2, s1)] = s3
                    return result
            elif s1[0] == s3[0]:
                # s1의 첫 번째 문자와 s3의 첫 번째 문자가 같은 경우
                result = helper(s1[1:], s2, s3[1:])
                if result:
                    hist[(s1, s2)] = s3
                    hist[(s2, s1)] = s3
                else:
                    hist_no[(s1, s2)] = s3
                    hist_no[(s2, s1)] = s3
                return result
            elif s2[0] == s3[0]:
                # s2의 첫 번째 문자와 s3의 첫 번째 문자가 같은 경우
                result = helper(s1, s2[1:], s3[1:])
                if result:
                    hist[(s1, s2)] = s3
                    hist[(s2, s1)] = s3
                else:
                    hist_no[(s1, s2)] = s3
                    hist_no[(s2, s1)] = s3
                return result
            
            return False

        return helper(s1, s2, s3)

4. 다른 풀이

• 2차원 DP를 이용한다.
• dp[i][j]가 s1[:i]와 s2[:j]로 s3[:i+j]를 만들 수 있는 지 없는 지를 나타낸다고 하자.
• 그렇다면 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])임을 이용하여 2차원 행렬을 모두 채울 수 있고 가장 오른쪽 끝 값을 반환하면 된다.

class Solution:
    def isInterleave(self, s1: str, s2: str, s3: str) -> bool:
        m, n, l = len(s1), len(s2), len(s3)
        if m + n != l:
            return False
        
        dp = [[False] * (n + 1) for _ in range(m + 1)]
        dp[0][0] = True
        
        for i in range(1, m + 1):
            dp[i][0] = dp[i-1][0] and s1[i-1] == s3[i-1]
        
        for j in range(1, n + 1):
            dp[0][j] = dp[0][j-1] and s2[j-1] == s3[j-1]
        
        for i in range(1, m + 1):
            for j in range(1, n + 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[m][n]

---

• 1차원 DP를 이용하는 풀이
• 2차원 DP 풀이에서 dp[i][j]의 값은 dp[i-1][j]와 dp[i][j-1]에 의해 정해짐을 알 수 있다. 따라서 2차원 행렬을 모두 만들 필요 없고 필요한 것만 기록하여 1차원 DP를 할 수 있다.

class Solution:
    def isInterleave(self, s1: str, s2: str, s3: str) -> bool:
        m, n, l = len(s1), len(s2), len(s3)
        if m + n != l:
            return False
        
        if m < n:
            return self.isInterleave(s2, s1, s3)
        
        dp = [False] * (n + 1)
        dp[0] = True
        
        for j in range(1, n + 1):
            dp[j] = dp[j-1] and s2[j-1] == s3[j-1]
        
        for i in range(1, m + 1):
            dp[0] = dp[0] and s1[i-1] == s3[i-1]
            for j in range(1, n + 1):
                dp[j] = (dp[j] and s1[i-1] == s3[i+j-1]) or (dp[j-1] and s2[j-1] == s3[i+j-1])
        
        return dp[n]

---

• 재귀 이용한 풀이

class Solution:
    def isInterleave(self, s1: str, s2: str, s3: str) -> bool:
        m, n, l = len(s1), len(s2), len(s3)
        if m + n != l:
            return False
        
        memo = {} 
        
        def helper(i: int, j: int, k: int) -> bool:
            if k == l:
                return True
            
            if (i, j) in memo:
                return memo[(i, j)]
            
            ans = False
            if i < m and s1[i] == s3[k]:
                ans = ans or helper(i + 1, j, k + 1)
                
            if j < n and s2[j] == s3[k]:
                ans = ans or helper(i, j + 1, k + 1)
            
            memo[(i, j)] = ans
            return ans
        
        return helper(0, 0, 0)

5. 배운점 

• 항상 DP를 떠올리기 힘들다.
• 부분을 해결하는 것이 전체를 풀 때 도움이 된다면 DP를 떠올려 보자.