97. Interleaving String

[zeikar]

Problem link

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

Problem Summary

s1과 s2 스트링을 자른 다음 교대로 이어 붙여서 s3 스트링을 만들수 있는지 판단하는 문제.

예시는: s1 = "aabcc", s2 = "dbbca", s3 = "aadbbcbcac"

Solution

전형적인 DP 문제이다.
현재까지 고른 s1의 인덱스, s2의 인덱스, 마지막으로 고른 스트링 (s1 / s2) 해서 죽 돌려보았다.

DP[i][j][k] = i: s1 인덱스, j: s2 인덱스, k: 마지막으로 고른 스트링

그런데 여기서 최적화가 가능한데 s1, s2 교대로 골라야 해서 마지막으로 고른 스트링을 저장했는데 사실 필요 없다. s1 다음에 s1를 또 골랐다고 해도 이를 한 덩어리로 보고 s1를 한 번만 골랐다고 생각해주면 된다.

DP[i][j] = i: s1 인덱스, j: s2 인덱스

실제로 제출 시 소요시간이 3배 정도 단축됨.

Follow up 문제로 공간복잡도를 O(s2.length) 까지 줄여보라는 것이 있는데 이를 하려면 Top-Down (재귀방식) DP로는 불가능하고 Bottom-up으로 구현하면 좀 복잡하지만 가능하다.

Source Code

from functools import cache


class Solution:
    def isInterleave(self, s1: str, s2: str, s3: str) -> bool:
        if len(s1) + len(s2) != len(s3):
            return False

        @cache
        def solve(s1Index: int, s2Index: int) -> bool:
            if s1Index + s2Index >= len(s3):
                return True

            res = False
            s3Index = s1Index + s2Index
            if s1Index < len(s1) and s1[s1Index] == s3[s3Index]:
                res |= solve(s1Index + 1, s2Index)
            if s2Index < len(s2) and s2[s2Index] == s3[s3Index]:
                res |= solve(s1Index, s2Index + 1)
            return res

        return solve(0, 0) or solve(0, 0)