HomeLeetcode97. Interleaving String - Leetcode Solutions
Leetcode

97. Interleaving String – Leetcode Solutions

Declan Clarke

Description:

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 = s1 + s2 + ... + sn
  • t = t1 + t2 + ... + tm
  • |n - m| <= 1
  • The interleaving is s1 + t1 + s2 + t2 + s3 + t3 + ... or t1 + s1 + t2 + s2 + t3 + s3 + ...

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

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

Solution in Python:

Approach:

  1. Check Lengths:
    • First, check if the lengths of s1 and s2 sum up to the length of s3. If not, s3 cannot be an interleaving of s1 and s2.
  2. Define DP Table:
    • Use a 2D boolean DP table dp where dp[i][j] represents 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.
  3. Initialization:
    • dp[0][0] is True because two empty strings can form an empty string.
    • Initialize the first row and first column based on the prefixes of s1 and s2.
  4. Fill DP Table:
    • Iterate over the DP table, and for each cell dp[i][j], check:
      • If s1[i-1] matches s3[i+j-1] and dp[i-1][j] is True, then dp[i][j] is True.
      • If s2[j-1] matches s3[i+j-1] and dp[i][j-1] is True, then dp[i][j] is True.
  5. Result:
    • The value at dp[len(s1)][len(s2)] will be the answer.
Python
class Solution:
    def isInterleave(self, s1: str, s2: str, s3: str) -> bool:
        # Check if the total length matches
        if len(s1) + len(s2) != len(s3):
            return False
        
        # Initialize the DP table
        dp = [[False] * (len(s2) + 1) for _ in range(len(s1) + 1)]
        
        # Set the base case
        dp[0][0] = True
        
        # Initialize the first row
        for i in range(1, len(s1) + 1):
            dp[i][0] = dp[i-1][0] and s1[i-1] == s3[i-1]
        
        # Initialize the first column
        for j in range(1, len(s2) + 1):
            dp[0][j] = dp[0][j-1] and s2[j-1] == s3[j-1]
        
        # Fill the DP table
        for i in range(1, len(s1) + 1):
            for j in range(1, len(s2) + 1):
                dp[i][j] = (dp[i-1][j] and s1[i-1] == s3[i+j-1]) or (dp[i][j-1] and s2[j-1] == s3[i+j-1])
        
        # The answer is at dp[len(s1)][len(s2)]
        return dp[len(s1)][len(s2)]

Explanation:

  • Length Check: If the sum of the lengths of s1 and s2 does not equal the length of s3, return False.
  • DP Initialization: Create a 2D list dp with dimensions (len(s1)+1) x (len(s2)+1) and initialize all values to False.
  • Base Case: Set dp[0][0] to True because two empty strings can interleave to form an empty string.
  • First Row and Column: Initialize the first row and column of the DP table based on whether the prefixes of s1 and s2 can match the corresponding prefix of s3.
  • Fill DP Table: For each cell in the table, check if the current character of s3 matches the current character of s1 or s2 and update the DP table accordingly.
  • Result: Return the value at dp[len(s1)][len(s2)], which indicates if s3 can be formed by interleaving s1 and s2.

This approach ensures that the solution is computed efficiently using dynamic programming.

Solution in Javascript:

JavaScript
/**
 * @param {string} s1
 * @param {string} s2
 * @param {string} s3
 * @return {boolean}
 */
var isInterleave = function(s1, s2, s3) {
    // Check if the total length matches
    if (s1.length + s2.length != s3.length) {
        return false;
    }

    // Initialize the DP table
    const dp = Array(s1.length + 1).fill(null).map(() => Array(s2.length + 1).fill(false));

    // Base case
    dp[0][0] = true;

    // Initialize the first row
    for (let i = 1; i <= s1.length; i++) {
        dp[i][0] = dp[i-1][0] && s1[i-1] === s3[i-1];
    }

    // Initialize the first column
    for (let j = 1; j <= s2.length; j++) {
        dp[0][j] = dp[0][j-1] && s2[j-1] === s3[j-1];
    }

    // Fill the DP table
    for (let i = 1; i <= s1.length; i++) {
        for (let j = 1; j <= s2.length; j++) {
            dp[i][j] = (dp[i-1][j] && s1[i-1] === s3[i+j-1]) || (dp[i][j-1] && s2[j-1] === s3[i+j-1]);
        }
    }

    // The result is in dp[s1.length][s2.length]
    return dp[s1.length][s2.length];
};

Solution in Java:

Java
class Solution {
    public boolean isInterleave(String s1, String s2, String s3) {
        // Check if the total length matches
        if (s1.length() + s2.length() != s3.length()) {
            return false;
        }

        // Initialize the DP table
        boolean[][] dp = new boolean[s1.length() + 1][s2.length() + 1];

        // Base case
        dp[0][0] = true;

        // Initialize the first row
        for (int i = 1; i <= s1.length(); i++) {
            dp[i][0] = dp[i - 1][0] && s1.charAt(i - 1) == s3.charAt(i - 1);
        }

        // Initialize the first column
        for (int j = 1; j <= s2.length(); j++) {
            dp[0][j] = dp[0][j - 1] && s2.charAt(j - 1) == s3.charAt(j - 1);
        }

        // Fill the DP table
        for (int i = 1; i <= s1.length(); i++) {
            for (int j = 1; j <= s2.length(); j++) {
                dp[i][j] = (dp[i - 1][j] && s1.charAt(i - 1) == s3.charAt(i + j - 1)) ||
                           (dp[i][j - 1] && s2.charAt(j - 1) == s3.charAt(i + j - 1));
            }
        }

        // The result is in dp[s1.length()][s2.length()]
        return dp[s1.length()][s2.length()];
    }
}

Solution in C#:

C#
public class Solution {
    public bool IsInterleave(string s1, string s2, string s3) {
        // Check if the total length matches
        if (s1.Length + s2.Length != s3.Length) {
            return false;
        }

        // Initialize the DP table
        bool[,] dp = new bool[s1.Length + 1, s2.Length + 1];

        // Base case
        dp[0, 0] = true;

        // Initialize the first row
        for (int i = 1; i <= s1.Length; i++) {
            dp[i, 0] = dp[i - 1, 0] && s1[i - 1] == s3[i - 1];
        }

        // Initialize the first column
        for (int j = 1; j <= s2.Length; j++) {
            dp[0, j] = dp[0, j - 1] && s2[j - 1] == s3[j - 1];
        }

        // Fill the DP table
        for (int i = 1; i <= s1.Length; i++) {
            for (int j = 1; j <= s2.Length; j++) {
                dp[i, j] = (dp[i - 1, j] && s1[i - 1] == s3[i + j - 1]) ||
                           (dp[i, j - 1] && s2[j - 1] == s3[i + j - 1]);
            }
        }

        // The result is in dp[s1.Length, s2.Length]
        return dp[s1.Length, s2.Length];
    }
}

Related Post

Subscribe
Notify of

0 Comments
Inline Feedbacks
View all comments

Popular

© 2024 Devexplain.com