97. Interleaving String

# Hard 太难了

How to define interLeave[i][j] is the key. Two-sequence DP problem. interLeave[i][j] means s1[:i] and s2[:j] can completely match string of s3[:i+j]. bool value.

如何实现 interLeave[i][j]，如何做这道题，取决于如何定义interLeave这种有循环直奔结果的数组，并且正确的初始化第一个元素

Solution:

1. Initilize interLeave[len(s1)+1][len(s2)+1], interLeave[i][0] and interLeave[0][j]

2. Two cases can match:

   1. s1[i] = s3[i+j] and interLeave[i-1][j]=True

   2. s2[j] = s3[i+j] and interLeave[i][j-1]=True

   Then interLeave[i][j] = True

Python

class Solution:
    def isInterleave(self, s1: str, s2: str, s3: str) -> bool:
        # edge case
        if len(s1)+len(s2) != len(s3):
            return False
        
        # interLeave[i][j] means if first i of s1 and j of s2 can be first (i+j) of s3 interleaving string
        # initialize interLeave
        interLeave = [[False]*(len(s2)+1) for i in range(len(s1)+1)]
        interLeave[0][0] = True
        for i in range(1, len(s1)+1):
            if s1[:i] == s3[:i]:
                interLeave[i][0] = True
        for j in range(1, len(s2)+1):
            if s2[:j] ==  s3[:j]:
                interLeave[0][j] = True
                
        # copmute
        for i in range(1, len(s1)+1):
            for j in range(1, len(s2)+1):
                if s1[i-1] == s3[i+j-1] and interLeave[i-1][j] == True:
                    interLeave[i][j] = True
                if s2[j-1] == s3[i+j-1] and interLeave[i][j-1] == True:
                    interLeave[i][j] = True

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

Java

Don't forget edge case, which can save a lot of time.