1173. Interleaving String

Given strings s1, s2, and s3, determine whether s3 can be formed by interleaving s1 and s2 while preserving the left-to-right order of each. Return true or false. The input is JSON {s1, s2, s3}.

Input: JSON {s1, s2, s3}.

Output: Boolean — true or false.

Examples

Input: {"s1":"aabcc","s2":"dbbca","s3":"aadbbcbcac"}
Output: true
Explanation: A valid interleaving exists.

Input: {"s1":"aabcc","s2":"dbbca","s3":"aadbbbaccc"}
Output: false
Explanation: No interleaving matches.

Input: {"s1":"","s2":"","s3":""}
Output: true
Explanation: All empty.

Constraints

• 0<=|s1|,|s2|<=100

Asked by