本文共 1323 字，大约阅读时间需要 4 分钟。

?????????s1?s2?s3???s1?s2????????????????????????????????????????????????????????

???????

????

class Solution:
    def isInterleave(self, s1, s2, s3):
        if len(s1) + len(s2) != len(s3):
            return False
        self.s1 = s1
        self.s2 = s2
        self.s3 = s3
        return self.dfs(0, 0, 0)
    def dfs(self, i, j, k):
        if k == len(self.s3):
            return i == len(self.s1) and j == len(self.s2)
        if i < len(self.s1) and self.s3[k] == self.s1[i]:
            if self.dfs(i + 1, j, k + 1):
                return True
        if j < len(self.s2) and self.s3[k] == self.s2[j]:
            if self.dfs(i, j + 1, k + 1):
                return True
        return False

????

• ??????isInterleave????????s1?s2????????s3?????????????False?

• ????????????dfs??????i=0, j=0, k=0?????s1?s2?s3??????

• ?????dfs?????????s1?s2?s3?????????????????k?????????????i?j????????????True?False?

• ?????????s3???????s1?s2??????????????????????????????????False?

??????????????????????????????????O(n)????????