Leetcode 97. 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 s and t are divided into n and m 
substrings
 respectively, 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.

세개의 문자열 s1, s2, s3이 주어집니다.
s3이 s1과 s2 두개를 끼워맞춰서 생성되는지 여부를 리턴하세요
두 문자열을 끼워 맞춘다는것은 s1과 s2를 부분문자열로 분리했을때, 이들을 순서대로 사용해 s3을 조립할수 있어야 합니다.

예시

Input: s1 = "aabcc", s2 = "dbbca", s3 = "aadbbcbcac"
Output: true

제한

• $0 <= s1.length, s2.length <= 100$
• $0 <= s3.length <= 200$
• s1, s2, s3은 영어 소문자로 이루어진다.

풀이

EDGE CASE

• s1의 길이가 0이면 s2와 s3를 비교한다.
• s2의 길이가 0이면 s1과 s3를 비교한다.
• 둘다 길이가 0이면 s3의 길이가 0인지를 확인한다.
• s1의 길이와 s2의 길이의 합이 s3의 길이와 일치해야 한다.

풀이는 Dynamic programming 을 사용한다.
먼저 2차원 배열이 필요한데, 2차원 배열의 크기는 행이 s1길이 + 1, 열이 s2길이 + 1 이 되도록 했다.
그렇게 나온 dp 배열의 뜻은 dp[i][j] 에 대해 s1에서 i개의 문자를 가져오고, s2에서 j개의 문자를 가져와 s3의 앞부분을 만들수 있는가를 저장한다.

여기서 dp[0][0]에 대해 먼저 생각해 볼수 있는데, s1과 s2에서 한개도 가져오지 않았다면 문제도 생길리 없기에 True가 들어간다.

이 후 빈 부분을 채워 넣으면 된다.

class Solution:
    def isInterleave(self, s1: str, s2: str, s3: str) -> bool:

        if s1 == "":
            return s2 == s3
        elif s2 == "":
            return s1 == s3
        elif s1 == "" and s2 == "":
            return s3 == ""
        
        if len(s1) + len(s2) != len(s3):
            return False

        dp = [[False for _ in range(len(s2) + 1)] for _ in range(len(s1) + 1)]

        for one in range(len(s1) + 1):
            for two in range(len(s2) + 1):
                if one == 0 and two == 0:
                    dp[one][two] = True
                elif one == 0 and two != 0:
                    dp[one][two] = dp[one][two-1] and s2[two-1] == s3[one + two - 1]
                elif two == 0 and one != 0:
                    dp[one][two] = dp[one-1][two] and s1[one-1] == s3[one + two - 1]
                else:
                    dp[one][two] = (dp[one-1][two] and s1[one-1] == s3[one + two - 1]) or (dp[one][two-1] and s2[two-1] == s3[one + two - 1])

        return dp[len(s1)][len(s2)]

• dp[one-1][two] and s1[one-1] == s3[one + two - 1]
  • s1의 문자 하나를 s3과 비교했을때 맞는지, s1에서 하나를 가져오기 전에는 성립하는지