Interleaving String

c is an interleaving of a and b if its characters can be split into two subsequences, one spelling a and the other spelling b, using every character of c exactly once. Return True if c is an interleaving of a and b.

For a = "aabcc", b = "dbbca" and c = "aadbbcbcac" the answer is True.

Examples

Example 1

Input:

is_interleave('aabcc', 'dbbca', 'aadbbcbcac')

Output:

True

Example 2

Input:

is_interleave('aabcc', 'dbbca', 'aadbbbaccc')

Output:

False

Constraints

• 0 <= len(a), len(b) <= 500
• 0 <= len(c) <= 1000
• Lower-case letters.