Today's Challenge

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

Interleaving String - LeetCode

Medium인데 어렵네... 몇 번 실패하고 결국 솔루션 봄.
결국 DFS로 풀어야 되네.
처음에 내 아이디어는 뒤에서부터 하나 씩 idx를 줄여가는 거였는데
그러면 분기되는 부분이 많아서 답을 찾기는 힘들 듯. 전체 탐색을 해야 하는구먼..

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

        @cache
        def dfs(i, j):
            if i == len(s1) and j == len(s2):
                return True
            cs1, cs2 = False, False
            if i < len(s1) and s1[i] == s3[i + j]:
                cs1 = dfs(i + 1, j)
            if j < len(s2) and s2[j] == s3[i + j]:
                cs2 = dfs(i, j + 1)
            return cs1 or cs2

        return dfs(0, 0)