97. Interleaving String Leetcode Java

Given s1, s2, s3, find whether s3 is formed by the interleaving of s1 and s2.

For example,
Given:
s1 = "aabcc",
s2 = "dbbca",

When s3 = "aadbbcbcac", return true.
When s3 = "aadbbbaccc", return false.

Solution:

Dynamic programming.

It is not hard to get that if s3[i+j-1] is interleaving string of s1[i],s2[j], where i is the substring length of s1, j is the substring length of s2. Then s3[i+j] is interleaving string of s1[i+1],s2[j] only if s3.nextchar=s1.nextchar. so res[i+1][j+1]=res[i][j+1] && s1.charAt(i)==s3.charAt(i+j+1)||res[i+1][j] && s2.charAt(j)==s3.charAt(i+j+1).

We can initialize the res[0][0]=true, and avoid to take special care of charAt(0).

Also, since we only need the final result, we can use a 1-d array as the DP array to save some space.

Time complexity: O(l1*l2), extra space: O(l2). Actually, we can manually choose the length of shorter string as the length of DP array to save more space.

 public boolean isInterleave(String s1, String s2, String s3) {  
    if(s1==null || s2==null || s3==null || s3.length()!=s1.length()+s2.length()) return false;  
    int l1=s1.length();  
    int l2=s2.length();  
    boolean[] res= new boolean[l2+1];  
    res[0]=true;  
    for(int j=0;j<l2 && s2.charAt(j)==s3.charAt(j);j++) res[j+1]=true;  
    for(int i=0;i<l1;i++){  
      res[0]=res[0] && s1.charAt(i)==s3.charAt(i);  
      for(int j=0;j<l2;j++){  
        res[j+1]=(res[j+1] && s1.charAt(i)==s3.charAt(i+j+1)) ||(res[j] && s2.charAt(j)==s3.charAt(i+j+1));  
      }  
    }  
    return res[l2];  
   }