LeetCode InterLeaving String

DP
Firstly, we don't care about the space and find a careful memorization.
Second, optimize the space complexity.

The character is either from s1 or s2.
DP[i][j] = (s1.charAt(i-1)==s3.charAt(i+j-1) && DP[i-1][j]) || (s2.charAt(j-1)==s3.charAt(i+j-1) && DP[i][j-1]);

DP[i][j] = true;
Means s3.substring(0, i+j-1) can be displayed by s1.substring(0,i) and s2,substring(0,j)

Here is the solution.
public boolean isInterleave(String s1, String s2, String s3) {
        // IMPORTANT: Please reset any member data you declared, as
        // the same Solution instance will be reused for each test case.
       
      if (s1==null || s2==null || s3==null) return false;
      int len1 = s1.length(), len2 = s2.length();
      if (s1.length()+s2.length() != s3.length()) return false;
      boolean dp[][] = new boolean[len1+1][len2+1];
      dp[0][0] = true;
      for (int i=1; i<=len1;i++) {
          if (s1.charAt(i-1)==s3.charAt(i-1) && dp[i-1][0]) {
              dp[i][0] = true;
          }
      }
     
      for (int j=1; j<=len2;j++) {
          if (s2.charAt(j-1)==s3.charAt(j-1) && dp[0][j-1]) {
              dp[0][j] = true;
          }
      }
     
      for (int i=1; i<=len1; i++) {
          for (int j=1; j<=len2; j++) {
              if (s1.charAt(i-1) == s3.charAt(i+j-1) && dp[i-1][j]) {
                  dp[i][j] = true;
              }
              if (s2.charAt(j-1) == s3.charAt(i+j-1) && dp[i][j-1]) {
                  dp[i][j] = true;
              }
          }
      }
      return dp[len1][len2];

}


Follow up:

I thought I am so diao to solve the 2D dynamic programming questions.
But here is some improvement for the current method. We don't really need O(mn) space. We can only use O(n) to maintain the status like DP[][].

For better solution, we can use the shorter array to store the status. O(min(m,n)).

Here is the solution.

public boolean isInterleave(String s1, String s2, String s3) {
        // IMPORTANT: Please reset any member data you declared, as
        // the same Solution instance will be reused for each test case.
       
      if (s1==null || s2==null || s3==null) return false;
      int len1 = s1.length(), len2 = s2.length();
      if (s1.length()+s2.length() != s3.length()) return false;
        String minWord = s1.length()>s2.length()?s2:s1;
        String maxWord = s1.length()>s2.length()?s1:s2;
        int lenMin = minWord.length();
        int lenMax = maxWord.length();
      boolean dp[] = new boolean[lenMin+1];
      dp[0] = true;
      for (int i=0; i<lenMin;i++) {
          dp[i+1] = minWord.charAt(i)==s3.charAt(i) && dp[i];
      }
     
      for (int i=0; i<lenMax; i++) {
          dp[0] = dp[0] && maxWord.charAt(i) == s3.charAt(i);
          for (int j=0; j<lenMin; j++) {
              dp[j+1] = dp[j+1]&& maxWord.charAt(i)==s3.charAt(i+j+1) || dp[j] && minWord.charAt(j)==s3.charAt(i+j+1);
          }
      }
      return dp[lenMin];

}