Interleaving Subsequence Checker

Given two strings str1 and str2, determine whether str2 can be formed by interleaving the characters of str1 with any arbitrary characters. In other words, check if str1 is a subsequence of str2.

A string A is a subsequence of a string B if there exist indices \(i_1, i_2, \ldots, i_k\) in \(B\) such that \(A[j] = B[i_j]\) for all valid \(j\) and \(i_1 < i_2 < \cdots < i_k\).

For example, given \(str1 = "abc"\) and \(str2 = "aebdc"\), the answer is True because one possible matching is \(a \rightarrow a, b \rightarrow b, c \rightarrow c\).

inputFormat

The input consists of two lines. The first line contains the string str1, and the second line contains the string str2.

outputFormat

Output a single line containing True if str1 is a subsequence of str2; otherwise, output False.

abc
aebdc

True