Question

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

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

An interleaving of two strings s and t is a configuration where s and t are divided into n and m substrings respectively, such that:

s = s₁ + s₂ + ... + s_n
t = t₁ + t₂ + ... + t_m
|n - m| <= 1
The interleaving is s₁ + t₁ + s₂ + t₂ + s₃ + t₃ + ... or t₁ + s₁ + t₂ + s₂ + t₃ + s₃ + ...

Note: a + b is the concatenation of strings a and b.

Example 1:

Input: s1 = "aabcc", s2 = "dbbca", s3 = "aadbbcbcac"
Output: true
Explanation: One way to obtain s3 is:
Split s1 into s1 = "aa" + "bc" + "c", and s2 into s2 = "dbbc" + "a".
Interleaving the two splits, we get "aa" + "dbbc" + "bc" + "a" + "c" = "aadbbcbcac".
Since s3 can be obtained by interleaving s1 and s2, we return true.

Example 2:

Input: s1 = "aabcc", s2 = "dbbca", s3 = "aadbbbaccc"
Output: false
Explanation: Notice how it is impossible to interleave s2 with any other string to obtain s3.

Example 3:

Input: s1 = "", s2 = "", s3 = ""
Output: true

Constraints:

0 <= s1.length, s2.length <= 100
0 <= s3.length <= 200
s1, s2, and s3 consist of lowercase English letters.

Follow up: Could you solve it using only O(s2.length) additional memory space?

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

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;
        }
    }
}


############

class Solution {
    private int m;
    private int n;
    private String s1;
    private String s2;
    private String s3;
    private Map<Integer, Boolean> memo = new HashMap<>();

    public boolean isInterleave(String s1, String s2, String s3) {
        m = s1.length();
        n = s2.length();
        this.s1 = s1;
        this.s2 = s2;
        this.s3 = s3;
        if (m + n != s3.length()) {
            return false;
        }
        return dfs(0, 0);
    }

    private boolean dfs(int i, int j) {
        System.out.println(i + ", " + j);
        if (i == m && j == n) {
            return true;
        }
        if (memo.containsKey(i * 100 + j)) {
            return memo.get(i * 100 + j);
        }

        boolean ret = (i < m && s1.charAt(i) == s3.charAt(i + j) && dfs(i + 1, j))
            || (j < n && s2.charAt(j) == s3.charAt(i + j) && dfs(i, j + 1));

        memo.put(i * 100 + j, ret);
        return ret;
    }
}

// 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:
    def isInterleave(self, s1: str, s2: str, s3: str) -> bool:
        if len(s1) + len(s2) != len(s3):  
            return False
        
        dp = [[False] * (len(s2) + 1) for _ in range(len(s1) + 1)]
        dp[0][0] = True
        
        for i in range(1, len(s1) + 1):
            dp[i][0] = s1[i - 1] == s3[i - 1] and dp[i - 1][0]
        for i in range(1, len(s2) + 1):
            dp[0][i] = s2[i - 1] == s3[i - 1] and dp[0][i - 1]
        
        # fill in dp array
        for i in range(1, len(s1) + 1):
            for j in range(1, len(s2) + 1):
                with_s1 = s1[i - 1] == s3[i + j - 1] and dp[i - 1][j]
                with_s2 = s2[j - 1] == s3[i + j - 1] and dp[i][j - 1]
                dp[i][j] = with_s1 or with_s2
        
        return dp[-1][-1]


class Solution: # dfs
    def isInterleave(self, s1: str, s2: str, s3: str) -> bool:
        m, n = len(s1), len(s2)
        if m + n != len(s3):
            return False

        @cache
        def dfs(i, j):
            if i == m and j == n:
                return True

            return (
                ( i < m and s1[i] == s3[i + j] and dfs(i + 1, j) )
                or 
                ( j < n and s2[j] == s3[i + j] and dfs(i, j + 1) )
            )

        return dfs(0, 0)

############

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)

func isInterleave(s1 string, s2 string, s3 string) bool {
	m, n := len(s1), len(s2)
	if m+n != len(s3) {
		return false
	}

	memo := make(map[int]bool)

	var dfs func(int, int) bool
	dfs = func(i, j int) bool {
		if i == m && j == n {
			return true
		}
		if v, ok := memo[i*100+j]; ok {
			return v
		}

		ret := (i < m && s1[i] == s3[i+j] && dfs(i+1, j)) ||
			(j < n && s2[j] == s3[i+j] && dfs(i, j+1))

		memo[i*100+j] = ret
		return ret
	}

	return dfs(0, 0)
}

using System;

public class Solution {
    public bool IsInterleave(string s1, string s2, string s3) {
        if (s1.Length + s2.Length != s3.Length) return false;
        var f = new bool[s3.Length + 1, s1.Length + 1];
        f[0, 0] = true;
        for (var i = 1; i <= s3.Length; ++i)
        {
            var j = Math.Max(0, i - s2.Length);
            var k = i - j;
            while (j <= s1.Length)
            {
                if (j > 0 && s3[i - 1] == s1[j - 1] && f[i - 1, j - 1])
                {
                    f[i, j] = true;
                }
                else if (k > 0 && s3[i - 1] == s2[k - 1] && f[i - 1, j])
                {
                    f[i, j] = true;
                }
                ++j;
                --k;
            }
        }
        
        for (var i = 0; i <= s1.Length; ++i)
        {
            if (f[s3.Length, i]) return true;
        }
        return false;
    }
}

97 - Interleaving String

Question

Algorithm

Code

All Problems

All Solutions

Welcome to Subscribe On Youtube

Question

Algorithm

Code

All Problems

All Solutions