Interleaving String

Problem Statement

The task is to determine whether a string s3 can be formed by interleaving two other strings s1 and s2. The concept of interleaving here involves splitting s1 and s2 into several substrings and reassembling these pieces intercalatedly to produce s3. Specifically, s1 and s2 are divided into substrings such that their concatenation in an alternate fashion results in s3. The interleaving pattern should either start with a substring from s1 followed by one from s2 or vice versa, continuing this pattern throughout. It's also required that the absolute difference in the number of pieces into which s1 and s2 are divided does not exceed one.

Examples

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.

Approach and Intuition

The key to solving the problem of checking if s3 is an interleaving of s1 and s2 lies in exploring all possible interleaved combinations that s1 and s2 can produce and seeing if any of these match s3. Below follows a logical breakdown based on insights from the examples provided:

1. Dynamic Programming Table Initialization:

   • Consider a 2D array dp where dp[i][j] indicates whether the first i characters of s1 and the first j characters of s2 can interleave to form the first i+j characters of s3.
   • Initialize dp[0][0] = true (empty strings interleaving to form an empty string).

2. Fill the DP Table:

   • For each character position in s1 and s2, determine if that character can extend an existing interleaving from s3.
   • Specifically, check if dp[i][j] = true under two conditions:
     • If the last character added from s1 matches the current character in s3 and dp[i-1][j] was true.
     • If the last character added from s2 matches the current character in s3 and dp[i][j-1] was true.

3. Edge Cases:

   • When one of s1 or s2 is empty, s3 should be entirely made of the other non-empty string.
   • If the combined length of s1 and s2 does not match the length of s3, it’s impossible for s3 to be an interleaving of s1 and s2.

Examples from user input demonstrate this logic:

• Example 1:

  • s1 = "aabcc", s2 = "dbbca", s3 = "aadbbcbcac"
  • Through careful selection and interleaving of substrings from s1 and s2, s3 is achievable.

• Example 2:

  • A mismatch in desired subsequence characters points to s3 not being a possible interleaving.

• Example 3:

  • All strings are empty. Trivially, an empty string is an interleaving of two empty strings.

Through this approach, one can systematically determine whether s3 is a result of interleaving s1 and s2 by filling up a dynamic programming table and consulting its last cell to check for feasibility. This method ensures that all potential segmentations and interleavings are considered.

Solutions

class Solution {
public:
    bool checkInterleavings(string str1, string str2, string str3) {
        int len1 = str1.length(), len2 = str2.length(), len3 = str3.length();
        if (len3 != len1 + len2) {
            return false;
        }
        vector<bool> interleaved(len2 + 1, false);
        for (int i = 0; i <= len1; i++) {
            for (int j = 0; j <= len2; j++) {
                if (i == 0 && j == 0) {
                    interleaved[j] = true;
                } else if (i == 0) {
                    interleaved[j] = interleaved[j - 1] && str2[j - 1] == str3[i + j - 1];
                } else if (j == 0) {
                    interleaved[j] = interleaved[j] && str1[i - 1] == str3[i + j - 1];
                } else {
                    interleaved[j] = (interleaved[j] && str1[i - 1] == str3[i + j - 1]) ||
                                     (interleaved[j - 1] && str2[j - 1] == str3[i + j - 1]);
                }
            }
        }
        return interleaved[len2];
    }
};