Given three strings input_str1, input_str2, and target_str, determine whether target_str can be formed by interleaving input_str1 and input_str2. An interleaving is defined as a sequence where input_str1 and input_str2 are split into non-empty substrings, and concatenated in alternating order, starting with either string, such that the difference in the number of substrings between input_str1 and input_str2 is at most 1. The concatenation of these substrings must equal target_str.
Example 1
Input: input_str1=abc, input_str2=def, target_str=adbcef
Output: True
Explanation: Splitting input_str1 as a, bc and input_str2 as d, ef, interleaving gives a+d+bc+ef = adbcef.
Example 2
Input: input_str1=xy, input_str2=z, target_str=xyz
Output: True
Explanation: Splitting input_str1 as x, y and input_str2 as z, interleaving gives x+z+y = xzy, but xyz can be formed by x+y+z.
Example 3
Input: input_str1=ab, input_str2=cd, target_str=acbd
Output: False
Explanation: No valid interleaving of ab and cd can produce acbd.
Example 4
Input: input_str1=', input_str2=abc, target_str=abc'
Output: True
Explanation: Empty input_str1, so target_str must equal input_str2.
Constraints
Case 1
Input: input_str1='pq', input_str2='rs', target_str='prqs'
Expected: False
Case 2
Input: input_str1='a', input_str2='b', target_str='ab'
Expected: True
Case 3
Input: input_str1='abc', input_str2='def', target_str='abcdef'
Expected: True
Case 4
Input: input_str1='', input_str2='', target_str=''
Expected: True
Case 5
Input: input_str1='abc', input_str2='def', target_str='abdecf'
Expected: False