Interleaving String In C,CPP,JAVA,PYTHON,C#,JS

/ DSA / By
Spread the love
Close-up of HTML code highlighted in vibrant colors on a computer monitor.

Problem Statement: Interleaving String

Given three strings, s1, s2, and s3, determine if s3 is formed by an interleaving of s1 and s2. An interleaving of two strings s1 and s2 is formed by inserting characters of s1 and s2 in such a way that the relative order of characters in both strings is preserved.

For example:

  • s1 = “abc”
  • s2 = “def”
  • s3 = “adbcef”

Here, s3 is an interleaving of s1 and s2, so the answer is True.

Constraints:

  • The length of s3 must be equal to the sum of lengths of s1 and s2. That is, len(s3) = len(s1) + len(s2).
  • Characters of s1 and s2 should appear in s3 while maintaining their relative order.

Dynamic Programming Approach

We can solve this problem using a 2D DP table.

  1. Let dp[i][j] represent whether the first i characters of s1 and the first j characters of s2 can form the first i+j characters of s3.
  2. Initialize dp[0][0] = True because an empty s1 and s2 can form an empty s3.
  3. The state transition will check whether s3[i+j-1] can be formed either by:
    • Taking a character from s1, i.e., if dp[i-1][j] is True and s1[i-1] == s3[i+j-1].
    • Taking a character from s2, i.e., if dp[i][j-1] is True and s2[j-1] == s3[i+j-1].

Time Complexity:

  • Time Complexity: O(m * n) where m is the length of s1 and n is the length of s2. This is because we fill a 2D DP table of size m+1 x n+1.
  • Space Complexity: O(m * n) due to the space required for the DP table.

Code Implementation in Different Languages

C:

#include <stdio.h>
#include <string.h>
#include <stdbool.h>

bool isInterleave(char *s1, char *s2, char *s3) {
    int m = strlen(s1);
    int n = strlen(s2);
    
    if (m + n != strlen(s3)) return false;

    bool dp[m + 1][n + 1];
    memset(dp, false, sizeof(dp));

    dp[0][0] = true;

    for (int i = 0; i <= m; i++) {
        for (int j = 0; j <= n; j++) {
            if (i > 0 && s1[i - 1] == s3[i + j - 1]) {
                dp[i][j] = dp[i][j] || dp[i - 1][j];
            }
            if (j > 0 && s2[j - 1] == s3[i + j - 1]) {
                dp[i][j] = dp[i][j] || dp[i][j - 1];
            }
        }
    }
    return dp[m][n];
}

int main() {
    char s1[] = "abc";
    char s2[] = "def";
    char s3[] = "adbcef";
    
    if (isInterleave(s1, s2, s3)) {
        printf("True\n");
    } else {
        printf("False\n");
    }
    return 0;
}

C++:

#include <iostream>
#include <vector>
#include <string>
using namespace std;

bool isInterleave(string s1, string s2, string s3) {
    int m = s1.size(), n = s2.size();
    if (m + n != s3.size()) return false;

    vector<vector<bool>> dp(m + 1, vector<bool>(n + 1, false));
    dp[0][0] = true;

    for (int i = 0; i <= m; i++) {
        for (int j = 0; j <= n; j++) {
            if (i > 0 && s1[i - 1] == s3[i + j - 1]) {
                dp[i][j] = dp[i][j] || dp[i - 1][j];
            }
            if (j > 0 && s2[j - 1] == s3[i + j - 1]) {
                dp[i][j] = dp[i][j] || dp[i][j - 1];
            }
        }
    }
    return dp[m][n];
}

int main() {
    string s1 = "abc", s2 = "def", s3 = "adbcef";
    if (isInterleave(s1, s2, s3)) {
        cout << "True" << endl;
    } else {
        cout << "False" << endl;
    }
    return 0;
}

Java:

public class Main {

    public static boolean isInterleave(String s1, String s2, String s3) {
        int m = s1.length(), n = s2.length();
        if (m + n != s3.length()) return false;

        boolean[][] dp = new boolean[m + 1][n + 1];
        dp[0][0] = true;

        for (int i = 0; i <= m; i++) {
            for (int j = 0; j <= n; j++) {
                if (i > 0 && s1.charAt(i - 1) == s3.charAt(i + j - 1)) {
                    dp[i][j] = dp[i][j] || dp[i - 1][j];
                }
                if (j > 0 && s2.charAt(j - 1) == s3.charAt(i + j - 1)) {
                    dp[i][j] = dp[i][j] || dp[i][j - 1];
                }
            }
        }
        return dp[m][n];
    }

    public static void main(String[] args) {
        String s1 = "abc", s2 = "def", s3 = "adbcef";
        System.out.println(isInterleave(s1, s2, s3) ? "True" : "False");
    }
}

Python:

def isInterleave(s1, s2, s3):
    m, n = len(s1), len(s2)
    if m + n != len(s3):
        return False
    
    dp = [[False] * (n + 1) for _ in range(m + 1)]
    dp[0][0] = True
    
    for i in range(m + 1):
        for j in range(n + 1):
            if i > 0 and s1[i - 1] == s3[i + j - 1]:
                dp[i][j] = dp[i][j] or dp[i - 1][j]
            if j > 0 and s2[j - 1] == s3[i + j - 1]:
                dp[i][j] = dp[i][j] or dp[i][j - 1]
    
    return dp[m][n]

# Example Usage
s1 = "abc"
s2 = "def"
s3 = "adbcef"
print("True" if isInterleave(s1, s2, s3) else "False")

C#:

using System;

class Program {
    public static bool IsInterleave(string s1, string s2, string s3) {
        int m = s1.Length, n = s2.Length;
        if (m + n != s3.Length) return false;

        bool[,] dp = new bool[m + 1, n + 1];
        dp[0, 0] = true;

        for (int i = 0; i <= m; i++) {
            for (int j = 0; j <= n; j++) {
                if (i > 0 && s1[i - 1] == s3[i + j - 1]) {
                    dp[i, j] = dp[i, j] || dp[i - 1, j];
                }
                if (j > 0 && s2[j - 1] == s3[i + j - 1]) {
                    dp[i, j] = dp[i, j] || dp[i, j - 1];
                }
            }
        }
        return dp[m, n];
    }

    static void Main() {
        string s1 = "abc", s2 = "def", s3 = "adbcef";
        Console.WriteLine(IsInterleave(s1, s2, s3) ? "True" : "False");
    }
}

JavaScript:

function isInterleave(s1, s2, s3) {
    const m = s1.length, n = s2.length;
    if (m + n !== s3.length) return false;

    const dp = Array.from({ length: m + 1 }, () => Array(n + 1).fill(false));
    dp[0][0] = true;

    for (let i = 0; i <= m; i++) {
        for (let j = 0; j <= n; j++) {
            if (i > 0 && s1[i - 1] === s3[i + j - 1]) {
                dp[i][j] = dp[i][j] || dp[i - 1][j];
            }
            if (j > 0 && s2[j - 1] === s3[i + j - 1]) {
                dp[i][j] = dp[i][j] || dp[i][j - 1];
            }
        }
    }
    return dp[m][n];
}

// Example Usage
let s1 = "abc", s2 = "def", s3 = "adbcef";
console.log(isInterleave(s1, s2, s3) ? "True" : "False");

Summary:

  • Problem: Check if a string s3 is an interleaving of strings s1 and s2.
  • Approach: Use a 2D DP table to solve this problem, checking whether each substring of s1 and s2 can form s3.
  • Time Complexity: O(m * n), where m is the length of s1 and n is the length of s2.
  • Space Complexity: O(m * n).