Question

Formatted question description: https://leetcode.ca/all/97.html

97	Interleaving String

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.

@tag-dp

Algorithm

Manually write out the two-dimensional array dp as follows:

Ø d b b c a
Ø T F F F F F
a T F F F F F
a T T T T T F
b F T T F T F
c F F T T T T
c F F F T F T

The major premise of this question is that the sum of the lengths of the strings s1 and s2 must be equal to the length of s3. If they are not equal, false is definitely returned.

Then when s1 and s2 are empty strings, s3 must be an empty string, and true is returned. So directly assign true to dp[0][0],

And then if one of s1 and s2 is an empty string, then the other must have the same length as s3, and then compare bitwise. If the same and the previous position is true, set True for dp, and assign False in other cases, so that the edge of the two-dimensional array dp is initialized.

Next, we only need to find the state transition equation to update the entire array. We found that at any non-edge position dp[i][j], its left or upper side may be True or False, and both sides can be updated. As long as there is a path through, then this point can be True. Then we have to look at it separately, if the left one is True, then we remove the character string s2[j-1] in the current corresponding s2 compared with the character in the corresponding position in s3 (when calculating the corresponding position, consider the matched The character in s1) is s3[j-1 + i]. If they are equal, then assign True, otherwise assign False. The situation where the above is True is similar, so the state transition equation can be calculated as:

dp[i][j] = (dp[i-1][j] && s1[i-1] == s3[i-1 + j]) || (dp[i][j-1] && s2 [j-1] == s3[j-1 + i]);

Where dp[i][j] indicates whether the first i characters of s2 and the first j characters of s1 match the first i+j characters of s3

Code

Java

public class Interleaving_String {

    public class Solution {
        public boolean isInterleave(String s1, String s2, String s3) {
            if (s1.length() == 0 || s1 == null) {
                return s2.equals(s3);
            }

            if (s2.length() == 0 || s2 == null) {
                return s1.equals(s3);
            }

            // @note: missed this simple check
            if (s1.length() + s2.length() != s3.length()) {
                return false;
            }

            // 1-to-i of s1, and 1-to-j of s2, can for 1-to-(i+j) of s3
            boolean[][] dp = new boolean[s1.length() + 1][s2.length() + 1]; // +1 for empty string

            dp[0][0] = true;

            // pre-process for empty string case
            for (int i = 1; i < s1.length() + 1; i++) {
                dp[i][0] = (s1.charAt(i - 1) == s3.charAt(i - 1))
                    && dp[i - 1][0];
            }
            for (int i = 1; i < s2.length() + 1; i++) {
                dp[0][i] = (s2.charAt(i - 1) == s3.charAt(i - 1))
                    && dp[0][i - 1];
            }

            for (int i = 1; i < s1.length() + 1; i++) {
                for (int j = 1; j < s2.length() + 1; j++) {

                    boolean withS1 = s1.charAt(i - 1) == s3.charAt(i - 1 + j) && dp[i - 1][j];
                    boolean withS2 = s2.charAt(j - 1) == s3.charAt(i - 1 + j) && dp[i][j - 1];

                    dp[i][j] = withS1 || withS2;
                }
            }

            return dp[s1.length()][s2.length()];
        }
    }


    public class Solution_over_time {
        public boolean isInterleave(String s1, String s2, String s3) {

            if (s1.length() == 0 || s1 == null) {
                return s2.equals(s3);
            }

            if (s2.length() == 0 || s2 == null) {
                return s1.equals(s3);
            }

            boolean withS1 = false;
            boolean withS2 = false;

            if (s1.charAt(0) == s3.charAt(0)) {
                withS1 = isInterleave(s1.substring(1), s2, s3.substring(1));
            }
            if (s2.charAt(0) == s3.charAt(0)) {
                withS2 = isInterleave(s1, s2.substring(1), s3.substring(1));
            }

            return withS1 || withS2;
        }
    }
}

// OJ: https://leetcode.com/problems/interleaving-string/
// Time: O(2^(M+N))
// Space: O(MN)
class Solution {
    int M, N;
    vector<vector<int>> m;
    int dfs(string &a, string &b, string &c, int i, int j) {
        if (i == M && j == N) return 1;
        if (m[i][j] != 0) return m[i][j];
        int val = -1;
        if (i < M && a[i] == c[i + j]) val = dfs(a, b, c, i + 1, j);
        if (val != 1 && j < N && b[j] == c[i + j]) val = dfs(a, b, c, i, j + 1);
        return m[i][j] = val;
    }
public:
    bool isInterleave(string s1, string s2, string s3) {
        M = s1.size(), N = s2.size();
        if (M + N != s3.size()) return false;
        m.assign(M + 1, vector<int>(N + 1));
        return dfs(s1, s2, s3, 0, 0) == 1;
    }
};

class Solution(object):
  def isInterleave(self, s1, s2, s3):
    """
    :type s1: str
    :type s2: str
    :type s3: str
    :rtype: bool
    """
    d = {}
    s3 = list(s3)
    if len(s1) + len(s2) != len(s3):
      return False

    def dfs(s1, i, s2, j, d, path, s3):
      if (i, j) in d:
        return d[(i, j)]

      if path == s3:
        return True

      if i < len(s1):
        if s3[i + j] == s1[i]:
          path.append(s1[i])
          if dfs(s1, i + 1, s2, j, d, path, s3):
            return True
          path.pop()
          d[(i + 1, j)] = False

      if j < len(s2):
        if s3[i + j] == s2[j]:
          path.append(s2[j])
          if dfs(s1, i, s2, j + 1, d, path, s3):
            return True
          path.pop()
          d[(i, j + 1)] = False

      return False

    return dfs(s1, 0, s2, 0, d, [], s3)

97 - Interleaving String

Question

Algorithm

Code

All Problems

All Solutions