NUHMAN.com

Introduction

LeetCode 97: Interleaving String is a problem that involves checking whether a string s3 is formed by interleaving two other strings s1 and s2. The strings s1 and s2 are interleaved in such a way that they maintain their relative order in the interleaved string s3.

This is a classic example of a dynamic programming problem where you need to determine if it's possible to interleave two strings in such a way that the resultant string has all the characters of both strings while maintaining their order.

Problem Statement

Given strings s1, s2, and s3, return true if s3 is formed by an interleaving of s1 and s2, or false otherwise.

• An interleaving of two strings s1 and s2 is formed by merging them into a single string in such a way that both strings retain their relative order.
• Note that a string s3 is considered to be formed by interleaving s1 and s2 if:

1. s3 contains all characters of s1 and s2.
2. The characters of s1 and s2 appear in the same order in s3.

Example:

go

Input: s1 = "abc", s2 = "def", s3 = "adbcef"
Output: true
Explanation: "adbcef" is an interleaving of "abc" and "def".

Input: s1 = "abc", s2 = "def", s3 = "abdecf"
Output: false
Explanation: "abdecf" is not an interleaving of "abc" and "def".

Approach:

Dynamic Programming Approach:

This problem can be solved efficiently using dynamic programming (DP). The idea is to use a 2D DP table to check whether it is possible to interleave s1 and s2 to form s3.

1. Initial Checks:

• First, check if the total length of s3 is equal to the sum of the lengths of s1 and s2. If not, return false immediately.
• If the lengths match, we proceed to create the DP table.

1. Dynamic Programming Table:

• We define a 2D DP table dp[i][j] where:
• dp[i][j] is true if the first i characters of s1 and the first j characters of s2 can form the first i + j characters of s3.
• The state transition is based on whether the characters of s1 or s2 match the corresponding characters in s3.

1. Base Case:

• If both s1 and s2 are empty, then s3 must also be empty, and the result is true.

1. Recursive Formula:

• If the character from s1 matches the current character in s3, we can inherit the solution from dp[i-1][j].
• If the character from s2 matches the current character in s3, we can inherit the solution from dp[i][j-1].

1. Final Result:

• The final result is found in dp[len(s1)][len(s2)], which tells us whether we can interleave the entire s1 and s2 to form s3.

Go Implementation

Dynamic Programming Solution

go

func isInterleave(s1 string, s2 string, s3 string) bool {
    // If the total length of s1 and s2 doesn't match the length of s3, return false
    if len(s1)+len(s2) != len(s3) {
        return false
    }

    // Initialize a 2D DP table with dimensions (len(s1)+1) x (len(s2)+1)
    dp := make([][]bool, len(s1)+1)
    for i := range dp {
        dp[i] = make([]bool, len(s2)+1)
    }

    // Initialize the base case
    dp[0][0] = true

    // Fill the DP table
    for i := 0; i <= len(s1); i++ {
        for j := 0; j <= len(s2); j++ {
            // Check if we can take a character from s1
            if i > 0 && s1[i-1] == s3[i+j-1] {
                dp[i][j] = dp[i][j] || dp[i-1][j]
            }
            // Check if we can take a character from s2
            if j > 0 && s2[j-1] == s3[i+j-1] {
                dp[i][j] = dp[i][j] || dp[i][j-1]
            }
        }
    }

    // The result is in dp[len(s1)][len(s2)]
    return dp[len(s1)][len(s2)]
}

Explanation:

1. Input and Base Case:

• First, we check if the lengths of s1 and s2 combined equal the length of s3. If they don't, we return false early because it's impossible for s3 to be an interleaving of s1 and s2.

1. Dynamic Programming Table:

• We create a 2D boolean array dp where each cell dp[i][j] represents whether the first i characters of s1 and the first j characters of s2 can form the first i + j characters of s3.

1. Filling the DP Table:

• We iterate over all possible lengths i and j for the two strings.
• For each combination of i and j, we check if:
• The character from s1[i-1] matches s3[i+j-1] and if the previous state dp[i-1][j] is true.
• The character from s2[j-1] matches s3[i+j-1] and if the previous state dp[i][j-1] is true.

1. Result:

• The final result is found in dp[len(s1)][len(s2)], which tells us whether we can interleave s1 and s2 to form s3.

Time and Space Complexity

MetricComplexityTime ComplexityO(m * n)Space ComplexityO(m * n)

Where:

• m is the length of s1, and n is the length of s2.
• Time Complexity: We need to fill a DP table of size (m+1) x (n+1), leading to a time complexity of O(m * n).
• Space Complexity: The space complexity is O(m * n) due to the storage required for the DP table.

Edge Cases

1. Empty Strings:

• Input: s1 = "", s2 = "", s3 = ""
• Output: true
• Explanation: An empty s3 is a valid interleaving of two empty strings.

1. Length Mismatch:

• Input: s1 = "abc", s2 = "def", s3 = "abdef"
• Output: false
• Explanation: The length of s3 must be the sum of the lengths of s1 and s2, so this input is invalid.

1. One String is Empty:

• Input: s1 = "abc", s2 = "", s3 = "abc"
• Output: true
• Explanation: If one string is empty, s3 should match the non-empty string exactly.

Conclusion

LeetCode 97: Interleaving String is a great problem for practicing dynamic programming. By breaking down the problem into smaller subproblems and using a 2D DP table, we can efficiently check if a string can be interleaved from two other strings. This approach ensures that we explore all possible interleavings without redundant calculations.

The solution has a time complexity of O(m * n) and space complexity of O(m * n), making it an optimal approach for this problem.