# String interleaving problem

String interleaving problem – You are given 3 strings. You have to tell if first and second string can interleave with each other to form 3rd string or not.

```Input : String s1 = "abc"; String s2 = "xyz"; String s12 = "axbycz";```

``` ```

`Output : true`

```package com.omt.learn.algo;

public class StringInterleaving {

public static void main(String[] args) {
String s1 = "abc";
String s2 = "xyz";
String s12 = "axbycz";

}

public static boolean isStringMadeOfTwoString(String s1, String s2, String s12) {

if (s1.length() + s2.length() != s12.length()) {
return true;
}

boolean[][] matrix = new boolean[s2.length() + 1][s1.length() + 1];
char c1[] = s1.toCharArray();
char c2[] = s2.toCharArray();
char c12[] = s12.toCharArray();

int maxSize = Math.max(s1.length(), s2.length());

matrix[0][0] = true;
for (int i = 1; i < maxSize + 1; i++) {
if (i < s2.length() + 1) {
if (c2[i - 1] == c12[i - 1] && matrix[i - 1][0]) {
matrix[i][0] = true;
}
}

if (i < s1.length() + 1) {
if (c1[i - 1] == c12[i - 1] && matrix[0][i - 1]) {
matrix[0][i] = true;
}
}
}

// printMatrix(matrix);

for (int i = 1; i < s2.length() + 1; i++) {
for (int j = 1; j < s1.length() + 1; j++) {
if (c1[j - 1] == c12[j + i - 1] && matrix[i][j - 1]) {
matrix[i][j] = true;
} else if (c2[i - 1] == c12[j + i - 1] && matrix[i - 1][j]) {
matrix[i][j] = true;
}

}
}

printMatrix(matrix);

return matrix[s2.length()][s1.length()];

}

public static void printMatrix(boolean[][] i) {
System.out.println("-------------");
for (boolean[] p : i) {
for (boolean px : p) {

System.out.print((px ? "T" : "F") + " ");

}
System.out.println("");
}
}

}
```