# Interleaving String

This page explains Java solution to problem `Interleaving String` using `Dynamic Programming` algorithm.

## Problem Statement

Given `s1`, `s2`, and `s3`, find whether `s3` is formed by the interleaving of `s1` and `s2`.

Example 1:

Input: s1 = "aabcc", s2 = "dbbca", s3 = "aadbbcbcac"
Output: true

Example 2:

Input: s1 = "aabcc", s2 = "dbbca", s3 = "aadbbbaccc"
Output: false

## Solution

If you have any suggestions in below code, please create a pull request by clicking here.
``````
package com.vc.hard;

class InterleavingString {
public boolean isInterleave(String s1, String s2, String s3) {
int m = s1.length();
int n = s2.length();
if(m + n != s3.length()) return false;
boolean[][] dp = new boolean[m + 1][n + 1];
for(int i = 0; i <= m; i++) {
for(int j = 0; j <= n; j++) {
if(i == 0 && j == 0) dp[i][j] = true;
else if(i == 0) {
dp[i][j] = dp[i][j - 1] && s3.charAt(i + j - 1) == s2.charAt(j - 1);
}
else if(j == 0) {
dp[i][j] = dp[i - 1][j] && s3.charAt(i + j - 1) == s1.charAt(i - 1);
}
else {
char requiredChar = s3.charAt(i + j - 1);
dp[i][j] = dp[i - 1][j] && requiredChar == s1.charAt(i - 1);
dp[i][j] = dp[i][j] || (dp[i][j - 1] && requiredChar == s2.charAt(j - 1));
}
}
}
return dp[m][n];
}
}
``````

## Time Complexity

O(M * N) Where
M is total number of elements in input string S1
N is total number of elements in input string S2

O(M * N)