[Leetcode 97] Interleaving String

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

1) 코드

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]

2) 해설

• 2차원 DP란 이런 것이다와 같은 2차원 DP의 정석과 같은 문제이다.
• 두 개의 문자열을 각각 dp2차원 배열의 row와 col이라고 생각하면 된다
• 그 다음에 s1에서 새로운 문자를 하나 추가할 때의 조건
  s2에서 새로운 문자를 하나 추가할 때의 조건을 잘 이해하고,
  그것을 2차원 DP에 업데이트해주면 된다.
• 여기서 dp[i][j]란 s1의 i번째 문자와 s2의 j번째 문자로
  s3를 i+j번째까지 만들 수 있는지에 대한 True/False 판단이라고
  보면 된다.