Say that two strings s1 and s2 can be merged into a third string s3 if s3 is obtained from s1 by inserting arbitrarily in s1 the characters in s2, respecting their order. For instance, the two strings ab and cd can be merged into abcd, or cabd, or cdab, or acbd, or acdb, ..., but not into adbc nor into cbda. Write a program merging_strings.py that prompts the user for 3 strings and displays the output as follows:

• If no string can be obtained from the other two by merging, then the program outputs that there is no solution.

• Otherwise, the program outputs which of the strings can be obtained from the other two by merging.

def one_char(a, b_list):

    for i in range(len(b_list)+1):

        tmp = b_list.copy()

        tmp.insert(i, a)

        yield tmp

def whole_char(a_list, b_list):

    if len(a_list) == 1:

        yield from one_char(a_list[0], b_list)

    else:

        for li in whole_char(a_list[1:], b_list):

            yield from one_char(a_list[0], li)

def is_merging(str_1, str_2, str_3):

    for tmp in [''.join(li) for li in whole_char(list(str_1), list(str_2))]:

        if tmp == str_3:

            return True

    return False

str1 = input("Please input the first string: ")

str2 = input("Please input the second string: ")

str3 = input("Please input the third string: ")

if is_merging(str1, str2, str3):

    print("The third string can be obtained by merging the other two.")

elif is_merging(str1, str3, str2):

    print("The second string can be obtained by merging the other two.")

elif is_merging(str2, str3, str1):

    print("The first string can be obtained by merging the other two.")

else:

    print("No solution")