[LeetCode] 97 | Interleaving String | Python

---

문제 링크: https://leetcode.com/problems/interleaving-string/

---

문제

Given strings s1, s2, and s3, find whether s3 is formed by an interleaving of s1 and s2.

An interleaving of two strings s and t is a configuration where they are divided into non-empty substrings such that:

• s = s1 + s2 + ... + sn
• t = t1 + t2 + ... + tm
• |n - m| <= 1
• The interleaving is s1 + t1 + s2 + t2 + s3 + t3 + ... or t1 + s1 + t2 + s2 + t3 + s3 + ...

Note: a + b is the concatenation of strings a and b.

---

조건

• 0 <= s1.length, s2.length <= 100
• 0 <= s3.length <= 200
• s1, s2, and s3 consist of lowercase English letters.

---

내 풀이

문제의 예시처럼

s1 = "aabcc", s2 = "dbbca", s3 = "aadbbcbcac"

라고 주어졌다고 생각하자.

위 그림과 같이 2차원 dp를 만든다.

---

가장 끝자리부터 s3과 비교하여 True나 False를 저장한다.

첫번째 열부터 채우는 것은 s1뒤에 s2를 그대로 붙여 s3이 되는지를 확인하는 것이고, 첫번째 행은 s2뒤에 s1을 그대로 붙이는 것이다.

예를 들면, 첫번째 열은 s1[0]==s3[0]이고, 바로 전의 dp[0][0]==True이기 때문에 dp[1][0]==True다.

s1[0]==s3[0]이라는 뜻은 아래 그림에서 첫번째 화살표를 만족한다는 것이다.

바로 전의 dp[0][0]==True라는 것은 이전까지는 모두 문제의 조건을 만족한다는 뜻이다.

이와 같은 방식으로 저 표를 채우다보면, dp[-1][-1]의 원소(T/F)에 따라 s1과 s2로 s3을 만들수있는지 여부가 결정된다.

---

코드

class Solution:
    def isInterleave(self, s1: str, s2: str, s3: str) -> bool:
        N1, N2 = len(s1), len(s2)
        if len(s3) != N1+N2:    return False
        
        dp = [[False]*(N2+1) for _ in range(N1+1)]
        dp[0][0] = True
        
        for n in range(1, N1+1):
            dp[n][0] = (s1[n-1] == s3[n-1]) and dp[n-1][0]
        
        for n in range(1, N2+1):
            dp[0][n] = (s2[n-1] == s3[n-1]) and dp[0][n-1]
        
        for n in range(1, N1+1):
            for m in range(1, N2+1):
                t1 = (s1[n-1] == s3[n+m-1]) and dp[n-1][m]
                t2 = (s2[m-1] == s3[n+m-1]) and dp[n][m-1]
                dp[n][m] = t1 or t2
                
        return dp[N1][N2]