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

/ DSA / By
Spread the love
Close-up of a laptop and tablet on a wooden desk, showcasing modern technology.

Problem Statement: Interleaving String

Given three strings s1, s2, and s3, the task is to determine if s3 is formed by interleaving s1 and s2 while maintaining the relative order of characters from both strings s1 and s2.

A string s3 is said to be an interleaving of s1 and s2 if:

  • s3 is of length |s1| + |s2|.
  • It contains all the characters of s1 and s2 in order, without changing the relative ordering of characters.

Example:

Example 1:

  • Input: s1 = "abc", s2 = "def", s3 = "adbcef"
  • Output: True
  • Explanation: The string “adbcef” can be formed by interleaving “abc” and “def”.

Example 2:

  • Input: s1 = "abc", s2 = "def", s3 = "abdecf"
  • Output: False
  • Explanation: The string “abdecf” cannot be formed by interleaving “abc” and “def” while preserving the order of characters.

Approach:

The problem can be solved using Dynamic Programming (DP). The key idea is to use a 2D DP table where 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.

Algorithm:

  1. Initialization:
    • Create a 2D DP table of size (len(s1) + 1) x (len(s2) + 1). Initialize dp[0][0] to True (i.e., an empty string can be formed from two empty strings).
  2. Filling the DP Table:
    • Iterate over each character in s1 and s2. For each pair (i, j):
      • Check if the character from s1[i-1] matches s3[i+j-1], and if dp[i-1][j] is True.
      • Similarly, check if the character from s2[j-1] matches s3[i+j-1], and if dp[i][j-1] is True.
  3. Final Answer:
    • After filling the DP table, the answer is stored in dp[len(s1)][len(s2)]. If it’s True, then s3 can be formed by interleaving s1 and s2; otherwise, it cannot.

Complexity:

  • Time Complexity: O(m * n), where m is the length of s1 and n is the length of s2. We need to fill the DP table of size (m+1) x (n+1) and each cell requires constant time.
  • Space Complexity: O(m * n) for the DP table.

Code Implementations:

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 (strlen(s3) != m + n) return false;
    
    bool dp[m+1][n+1];
    memset(dp, 0, 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-1][j];
            }
            if (j > 0 && s2[j-1] == s3[i+j-1]) {
                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 (s3.size() != m + n) 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-1][j];
            }
            if (j > 0 && s2[j-1] == s3[i+j-1]) {
                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\n";
    } else {
        cout << "False\n";
    }
    return 0;
}

Java:

public class InterleavingString {
    public static boolean isInterleave(String s1, String s2, String s3) {
        int m = s1.length(), n = s2.length();
        if (s3.length() != m + n) 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-1][j];
                }
                if (j > 0 && s2.charAt(j-1) == s3.charAt(i+j-1)) {
                    dp[i][j] |= dp[i][j-1];
                }
            }
        }
        
        return dp[m][n];
    }

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

Python:

def isInterleave(s1, s2, s3):
    m, n = len(s1), len(s2)
    if len(s3) != m + n:
        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 - 1][j]
            if j > 0 and s2[j - 1] == s3[i + j - 1]:
                dp[i][j] |= dp[i][j - 1]
    
    return dp[m][n]

# Test case
s1 = "abc"
s2 = "def"
s3 = "adbcef"
print(isInterleave(s1, s2, s3))  # Output: True

C#:

using System;

public class InterleavingString {
    public static bool IsInterleave(string s1, string s2, string s3) {
        int m = s1.Length, n = s2.Length;
        if (s3.Length != m + n) 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-1, j];
                }
                if (j > 0 && s2[j-1] == s3[i+j-1]) {
                    dp[i, j] |= dp[i, j-1];
                }
            }
        }
        
        return dp[m, n];
    }

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

JavaScript:

function isInterleave(s1, s2, s3) {
    let m = s1.length, n = s2.length;
    if (s3.length !== m + n) return false;
    
    let 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];
}

// Test case
let s1 = "abc", s2 = "def", s3 = "adbcef";
console.log(isInterleave(s1, s2, s3));  // Output: true

Summary:

  • Time Complexity: O(m * n)
  • Space Complexity: O(m * n)
  • The solution uses dynamic programming to fill a 2D table, checking whether each substring of s1 and s2 can form the corresponding prefix of s3.