97. Interleaving String

문제

https://leetcode.com/problems/interleaving-string/

코드

class Solution:
    def isInterleave(self, s1: str, s2: str, s3: str) -> bool:
        s1_len = len(s1)
        s2_len = len(s2)
        s3_len = len(s3)

        if s1_len + s2_len != s3_len:
            return False

        dp = [[True for _ in range(s1_len+1)] for _ in range(s2_len+1)]

        for i in range(1, s2_len+1):
            dp[i][0] = dp[i-1][0] and s2[i-1] == s3[i-1]

        for i in range(1, s1_len+1):
            dp[0][i] = dp[0][i-1] and s1[i-1] == s3[i-1]

        for i in range(1, s2_len+1):
            for j in range(1, s1_len+1):
                dp[i][j] = (dp[i-1][j] and s2[i-1] == s3[i-1+j]) or \
                            (dp[i][j-1] and s1[j-1] == s3[i-1+j])

        return dp[-1][-1]

피드백

• 일단 못품
• DP 문제였음
• 아이디어는 다음과 같다.
  • 각 string이 처음부터 어디까지 연속해서 나타날 수 있는지 확인
  • 결국 dp[i][j]에서 i와 j는 각각 한 스트링의 현재 커서를 나타내게 된다.
  • 그래서 dp[i][j]는 i-1에서 한 커서 움직여서 s3[i+j-1]까지 똑같음을 만족할 수 있는지,
  • 혹은 j-1에서 한 커서 움직여서 s3[i+j-1]까지 똑같음을 만족할 수 있는지를 확인하는 것이다.