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

class Solution {
    public boolean isInterleave(String s1, String s2, String s3) {
        if (s3.length() != s1.length() + s2.length()) {
            return false;
        }
        
        boolean[][] match = new boolean[s1.length()+1][s2.length()+1];
        match[0][0] = true;
        for(int i = 1; i <= s1.length(); i ++)
            if(s1.charAt(i-1) == s3.charAt(i-1) && match[i-1][0])
                match[i][0] = true;
        
        for(int j = 1; j <= s2.length(); j ++)
            if(s2.charAt(j-1) == s3.charAt(j-1) && match[0][j-1])
                match[0][j] = true;
        
        for(int i = 1; i <= s1.length(); i ++)
            for(int j = 1; j <= s2.length(); j ++) {
                if(j == 0)
                    
                if((s3.charAt(i+j-1) == s1.charAt(i-1)) && match[i-1][j])
                    match[i][j] = true;
                if((s3.charAt(i+j-1) == s2.charAt(j-1)) && match[i][j-1])
                    match[i][j] = true;
            }
        return match[s1.length()][s2.length()];
    }
}

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