example.jpg

输入：s1 = "aabcc", s2 = "dbbca", s3 = "aadbbcbcac"
输出：true

这道题一看就是动态规划，首先想到的状态是s3[:i]由s[:k1]、s[:k2]组成，这样[k1,k2]就可能有重复，下一次i+1，[_k1, _k2]就可能有重复，所以用hash判断重复。这儿应该也可以使用dfs来做。

这儿官方给出的是s[:k1]、s[:k2]是否能组成s3[:i]，就避免了判断重复= =。

class Solution:
    def isInterleave(self, s1: str, s2: str, s3: str) -> bool:
        # 思路 拆 + 合 （动态规划）
        # 1. 递推公式
        # dp[i] = s1[:k1] + s2[:k1]，dp[i]为多种情况的集合
        # dp[i] = s1[:k1+1] + s2[:k1] 或者 s1[:k1] + s2[:k1+1]

        # 2. 结束条件
        # dp[i] = s1 + s2且 i = len(s3) - 1

        # 3. 边界条件
        # i = 0

        num1 = len(s1)
        num2 = len(s2)

        num = len(s3)

        if num1 + num2 != num:
            return False

        if num1 == 0 or num2 == 0:
            if s1 + s2 == s3:
                return True
            else:
                return False

        memo = set()
        # hash值系数 k1*factor + k2
        factor = len(s2)

        i = 0
        now = []

        if s3[0] == s1[0]:
            hash_code = 0*factor + (-1)
            if not hash_code in memo:
                memo.add(hash_code)
                now.append([0, -1])

        if s3[0] == s2[0]:
            hash_code = -1*factor + 0
            if not hash_code in memo:
                memo.add(hash_code)
                now.append([-1, 0])

        if len(now) == 0:
            return False

        for i in range(1, num):
            memo = set()

            c = s3[i]

            pre = now
            now = []

            for pair in pre:
                i1 = pair[0]
                i2 = pair[1]
            
                if i1+1<num1 and c == s1[i1+1]:
                    hash_code = (i1+1)*factor + i2
                    if not hash_code in memo:
                        memo.add(hash_code)
                        now.append([i1+1, i2])

                if i2+1<num2 and c == s2[i2+1]:
                    hash_code = (i1)*factor + i2 + 1
                    if not hash_code in memo:
                        memo.add(hash_code)
                        now.append([i1, i2+1])

            # print('i, num, len(now):', i, num, len(now))
            # print('now[0]:', now[:20])

            if len(now) == 0:
                return False
            elif i == num-1:
                return True