New update is available. Click here to update.

Last Updated: 10 Dec, 2020

Difficulty: Hard

```
let A = a, B = ac, C = ac.
Now In this example, we can take whole string B to form C or take substring {a} and substring {c} from A and B, respectively to make C. Hence the answer is 2.
```

```
The first line contains a single integer ‘T’ denoting the number of test cases to be run. Then each test cases follow.
The first line of each test case contains a string ‘A’.
The Second line of the test case contains the string ‘B’.
The third line of the test case contains the string ‘C’.
```

```
For each test case, print a single integer ‘ANS’ representing the number of ways.
Output for each test case will be printed in a separate line.
```

```
You are not required to print anything; it has already been taken care of. Just implement the function and return the answer.
```

```
1 <= T <= 5
1 <= |A|, |B|, |C| <= 100, where |S| represents the length of the String S.
Time limit: 1 sec
```

The basic idea is to go through every element of the string **A** and **B** and check if the current element equals any element at some position in string **C**.

The steps are as follows:

- Create a function ‘recursion’ in which we will pass all the strings and their string length
**x**,**y**,**z**for strings**A**,**B**,**C**, respectively. - In the ‘recursion’ function:
- Iterate through the string
**A**from**x**to 0:(say iterator be i):- If the current element at
**x**of**A**is equal to the current element at**z**of**C**call the function for position**x**-1,**y**,**z**-1 and add it to the total ways.

- If the current element at
- Similarly, iterate through the string
**B**from**y**to 0:(say iterator be i):- If the current element at
**y**of B is equal to the current element at**z**of**C**call the function for position**x**,**y**-1,**z**-1 and add it to the total ways.

- If the current element at
- Return the total ways.

- Iterate through the string
- In the ‘Main’ function:
- Call the ‘recursion’ function.

This approach is same as the naive approach. The only difference is we will store all the results in an array **dp** to avoid repetitions.

The steps are as follows:

- Create a function ‘memoization’ in which we will pass all the strings and their string length
**x**,**y**,**z**for strings**A, B, C**, respectively. - In the ‘memoization’ function:
- Return
**dp[ x ][ y ][ z ]**if**dp[ x ][ y ][ z ]**is not equal to -1. - Iterate through the string A from
**x**to 0:(say iterator be i):- If the current element at
**x**of**A**is equal to the current element at**z**of**C**call the function for position**x**-1,**y**,**z**-1 and add it to**dp[ x ][ y ][ z ]**.

- If the current element at
- Similarly, iterate through the string
**B**from y to 0:(say iterator be i):- If the current element at
**y**of**B**is equal to the current element at**z**of**C**call the function for position**x**,**y**-1,**z**-1 and add it to**dp[ x ][ y ][ z ]**.

- If the current element at
- Return
**dp[ x ][ y ][ z ]**.

- Return
- In the ‘Main’ function:
- Initialize a 3D
**dp**of size**X, Y, Z**and initially make all the elements of the**dp**-1. - Call the ‘recursion’ function.
- Return
**dp[ x ][ y ][ z ]**.

- Initialize a 3D

In this approach, we will iterate over both the strings and check if the current element of the string matches with the current element of the final string and update the **dp **array.

- Initialize a 3D array
**dp**of size**(X + 1)*(Y + 1)*(Z + 1)**with value 0, where**X, Y, Z**is the size of strings**A**,**B**,**C**, respectively. - Update the value of
**dp**array with 1 for all positions of**X**and**Y**when**Z**is zero. - Iterate in a loop for string
**A**from 1 to**X**(say iterator be**i**) :- Iterate in a for loop for string
**B**from 1 to**Y**(say iterator be**j**) :- Iterate in a for loop for string
**C**from 1 to**Z**(say iterator be**k**) :- Iterate from 1 to
**i**(say iterator be**t**) and check if**A[t - 1]**is equal to**C[k - 1]**:- Update
**dp[ i ][ j ][ k ]**with**dp[ t - 1 ][ j ][ k - 1 ].**

- Update
- Similarly, Iterate from 1 to
**j**(say iterator be**t**) and check if B[**t**- 1] is equal to**C[k - 1]**:- Update
**dp[ i ][ j ][ k ]**with**dp[ i ][ l - 1 ][ k - 1 ].**

- Update

- Iterate from 1 to

- Iterate in a for loop for string

- Iterate in a for loop for string
- Return
**dp[ x ][ y ][ z ]**.

SIMILAR PROBLEMS

NINJA AND HAPPINESS

Posted: 9 Sep, 2022

Difficulty: Hard

DECODE STRING

Posted: 11 Sep, 2022

Difficulty: Moderate

Randomly Sorted

Posted: 13 Nov, 2022

Difficulty: Moderate

Search In A Sorted 2D Matrix

Posted: 23 Nov, 2022

Difficulty: Moderate

Spiral Matrix

Posted: 24 Nov, 2022

Difficulty: Easy

Popular Interview Problems: