leetcode medium : Interleaving String 공간 최적화하기

Interleaving String - LeetCode

Interleaving String - LeetCode

leetcode medium : Interleaving String :: Keep your pace (tistory.com)

leetcode medium : Interleaving String

 

아까 이 문제에 대한 글을 올리고 낮잠을 푸우우욱 잤다

그리고 다시 생각해봤는데 그리 어려울게 아닌거같았다

내가 메모화 재귀로 dp를 구현하고 거기서 최적화하려고 해서 어려웠던게 아닐까?

사실 edit distance같은것도 보면 bottom up dp로 구현하고 났을 때 

dp 행렬이 매 시점에 두 행밖에 안쓰이는 사실을 쉽게 발견할 수 있다.

이 문제도 bottom up으로 구현하면.. 보이지 않을까?

어쩌면 공간복잡도를 O(len(s2))로 줄여보라는 것은 공간복잡도를 줄이는 의미보다도

top down으로 한번, bottom up으로 한 번 구현해보라는 의미였을지도 모른다.

 

 

자 일단 저번 포스팅에서 dp[0][0]을 정답으로 두고 알고리즘을 설계했는데 이번엔 뒤집어서

dp[len(s1)][len(s2)]를 정답으로 두고 알고리즘을 설계해보자. 이래야 bottom up dp를 할때

iteration을 순방향으로 할 수 있다.

 

class Solution:
    def isInterleave(self, s1: str, s2: str, s3: str) -> bool:
        if len(s1) + len(s2) != len(s3):
            return False
        
        def search(i, j):
            if i == 0 and j == 0:
                return True
            
            b1 = b2 = False
            
            if i > 0:
                b1 |= s1[i - 1] == s3[i + j - 1] and search(i - 1, j)
                
            if j > 0:
                b2 |= s2[j - 1] == s3[i + j - 1] and search(i, j - 1)
            
            return b1 | b2
        
        return search(len(s1), len(s2))

 

메모화를 적용해보자.

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

 

 

 

자 이제 bottom up으로 바꿔보자.

base case는 DP(0,0) = True라는 것.

inductive하게 보면

DP(i + 1, j) |= DP(i, j) and s1[i] == s3[i + j]

DP(i, j + 1) |= DP(i, j) and s2[j] == s3[i + j]

 

참고로 DP(i, j)는 s1[:i]와 s2[:j]의 interleaving이 s3[ : i + j]인지 여부를 나타낸다.

 

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

 

이제 dp를 두 행만 사용하도록 바꾸면?

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

 

유레카!