Interleaving Strings 🎯

Welcome to a fascinating journey into the world of Data Structures and Algorithms! Today, we're going to delve into a captivating problem known as Interleaving Strings. By the end of this lesson, you'll have a solid understanding of this concept and how it can be applied in real-world projects.

What are Interleaving Strings? 📝

Interleaving strings is a problem where we are given three strings S1, S2, and S3, and the question is whether it's possible to obtain S3 by interleaving S1 and S2. Interleaving means inserting one string's characters between the characters of the other string.

Let's take an example to understand this better. Suppose we have S1 = "abc", S2 = "pqr", and S3 = "apbqrc". Here, S3 can be obtained by interleaving S1 and S2:

Insert p from S2 before a in S1, resulting in "apb" + "c" = "apbc"
Insert q from S2 before b in "apbc", resulting in "apqpbc"
Finally, insert r from S2 before c in "apqpbc", resulting in "apqpbrc", which is S3

The Algorithm 💡

The Interleaving Strings problem can be solved using dynamic programming. Here's a step-by-step approach to understand the algorithm:

Create a 3-dimensional boolean array dp[n+1][m+1][k+1] where n, m, and k are the lengths of S1, S2, and S3, respectively.
Initialize all values in the array to false. The base cases are:
- If any of the lengths n, m, or k is 0, then dp[n][m][k] is true if the other two strings are empty, and false otherwise.
For each valid index i from 1 to n, for each valid index j from 1 to m, and for each valid index k from 0 to n+m+1, we'll check whether S3[1..k] can be obtained by interleaving S1[1..i] and S2[1..j].
To do this, we'll consider three cases:
- If S1[i] == S3[k], then dp[i][j][k] is true and dp[i-1][j][k-1] is true.
- If S2[j] == S3[k], then dp[i][j][k] is true and dp[i][j-1][k-1] is true.
- If S1[i] != S3[k] and S2[j] != S3[k], then dp[i][j][k] is false.
Finally, if dp[n][m][k] is true, it means S3 can be obtained by interleaving S1 and S2.

Code Examples 💡

Here are two complete working examples in Python to help you get started:

Example 1: Brute Force Approach

python

def is_interleave(S1, S2, S3):
    if len(S1) + len(S2) != len(S3):
        return False

    def backtrack(i, j, k):
        if i == len(S1) and j == len(S2) and k == len(S3):
            return True

        if i < len(S1) and S1[i] == S3[k] and backtrack(i + 1, j, k + 1):
            return True

        if j < len(S2) and S2[j] == S3[k] and backtrack(i, j + 1, k + 1):
            return True

        return False

    return backtrack(0, 0, 0)

Example 2: Dynamic Programming Approach

python

def is_interleave_dp(S1, S2, S3):
    n, m, k = len(S1), len(S2), len(S3)

    dp = [[[False] * (k + 1) for _ in range(m + 1)] for _ in range(n + 1)]

    for i in range(n + 1):
        for j in range(m + 1):
            if not i or not j or not k:
                dp[i][j][0] = i and j and not k

            elif S1[i - 1] == S3[k - 1] and dp[i - 1][j][k - 1]:
                dp[i][j][k] = True
            elif S2[j - 1] == S3[k - 1] and dp[i][j - 1][k - 1]:
                dp[i][j][k] = True

    return dp[-1][-1][-1]

Quiz 💡

Wrapping Up 🎯

And that's a wrap on Interleaving Strings! This problem serves as a great introduction to dynamic programming and showcases the power of breaking down complex problems into smaller, manageable pieces. Keep practicing and experimenting with different strings to deepen your understanding. Happy coding! 🚀

📝 Note: You can find more resources on Interleaving Strings and other data structures and algorithms topics on CodeYourCraft. Keep learning and growing! 🚀