Given three strings S1, S2 and S3, write a program which checks whether S3 is an interleaving of S1 and S2.

Problem Note

• S3 is said to be interleaving S1 and S2 if it contains all characters of S1 and S2 and the order of all characters in individual strings is preserved.

Example 1

Input: S1 = "xxyzz", S2 = "wyyzx" and S3 = "xxwyyzyzxz"
Output: true
Explanation:"xx" (from S1) + "wyyz" (from S2) + "yz" (from S1) + "x" (from S2) + "z" (from S1)

Example 2

Input: S1 = "xxyzz", S2 = "wyyzx", S3 = "xxwyyyxzzz"
Output: false
Explanation: It is not possible to get S3 by interleaving S1 and S2.