leetcode medium : Interleaving String

Interleaving String - LeetCode

Interleaving String - LeetCode

 

딱~! 봐도 dp문제 ㅋㅋㅋㅋㅋ

 

일단 전체탐색으로 코딩

class Solution:
    def isInterleave(self, s1: str, s2: str, s3: str) -> bool:
        def search(i1, i2):
            i3 = i1 + i2

            if i3 == len(s3):
                return i1 == len(s1) and i2 == len(s2)
            
            b1 = b2 = False
            
            if i1 < len(s1) and s3[i3] == s1[i1]:
                b1 = search(i1 + 1, i2)
                
            if i2 < len(s2) and s3[i3] == s2[i2]:
                b2 = search(i1, i2 + 1)
                
            return b1 or b2
        
        return search(0, 0)

 

memoization 더하면 바로 dp가 됨

class Solution:
    def isInterleave(self, s1: str, s2: str, s3: str) -> bool:
        dp = [[None] * (len(s2) + 1) for _ in range(len(s1) + 1)]
        
        def search(i1, i2):
            i3 = i1 + i2
            
            if dp[i1][i2] != None:
                return dp[i1][i2]
            
            if i3 == len(s3):
                return i1 == len(s1) and i2 == len(s2)
            
            
            b1 = b2 = False

            if i1 < len(s1) and s3[i3] == s1[i1]:
                dp[i1 + 1][i2] = b1 = search(i1 + 1, i2)
                
            if i2 < len(s2) and s3[i3] == s2[i2]:
                dp[i1][i2 + 1] = b2 = search(i1, i2 + 1)
            return b1 or b2
        
        return search(0, 0)

 

근데 문제에 추가조건이 있다.. space complexity를 O( len(s1) * len(s2) )가 아닌 O(len(s2))로 줄여라..!

오 첨엔 어려울거라 생각했는데 생각해보니 당연히 O(len(s2))로 풀수가 있다.

만약 dp[s2]가 True이면 len(s1) + len(s2) == len(s3)이기만 하면 s3는 interleaving of s1 and s2가 될 수밖에 없다.

아 근데 어떻게 짜야될지 모르겠네...;;

 

아 진짜 어렵다;;

 

ㅏㅏㅏㅏㅏㅏㅏㅏㅏㅏㅏㅏㅏㅏㅏ진짬ㄴ이ㅏ럼닏하ㅓㅁ니ㅏㄷㅇ럼니ㅏㅇ럼ㅈ디ㅏㄹ

아

모르겠다..

 

 

다른 사람들 솔루션을 보자

 

나랑 같은 알고리즘의 top down solution

class Solution:
    def isInterleave(self, s1: str, s2: str, s3: str) -> bool:
        if len(s1) + len(s2) != len(s3): return False
        m, n = len(s1), len(s2)
        
        @lru_cache(None)
        def dp(i, j):
            if i == m and j == n: return True  # Found a valid match
            ans = False
            if i < m and s1[i] == s3[i+j]:  # Case match s1[i] with s3[i+j]
                ans |= dp(i + 1, j)
            if j < n and s2[j] == s3[i+j]:  # Case match s2[j] with s3[i+j]
                ans |= dp(i, j + 1)
            return ans

        return dp(0, 0)

 

bottom-up으로 변환한거

class Solution:
    def isInterleave(self, s1: str, s2: str, s3: str) -> bool:
        if len(s1) + len(s2) != len(s3): return False

        m, n = len(s1), len(s2)
        dp = [[False] * (n + 1) for _ in range(m + 1)]
        dp[m][n] = True
        for i in range(m, -1, -1):
            for j in range(n, -1, -1):
                if i < m and s1[i] == s3[i + j]:
                    dp[i][j] |= dp[i + 1][j]
                if j < n and s2[j] == s3[i + j]:
                    dp[i][j] |= dp[i][j + 1]
        return dp[0][0]

 

공간 최적화된 버전

class Solution:
    def isInterleave(self, s1: str, s2: str, s3: str) -> bool:
        if len(s1) + len(s2) != len(s3): return False

        m, n = len(s1), len(s2)
        dp, dpPrev = [False] * (n + 1), [False] * (n + 1)
        for i in range(m, -1, -1):
            for j in range(n, -1, -1):
                dp[j] = False
                if i == m and j == n:
                    dp[n] = True
                if i < m and s1[i] == s3[i + j]:
                    dp[j] |= dpPrev[j]
                if j < n and s2[j] == s3[i + j]:
                    dp[j] |= dp[j + 1]
            dp, dpPrev = dpPrev, dp
        return dpPrev[0]

 

ㅇㅇ 봐도 모르겠다 ㅋㅋㅋㅋㅋ