Intertwined Strings

View as PDF

Submit solution

All submissions

Best submissions

Points: 7 (partial)

Time limit: 2.0s

Memory limit: 512M

Author:

uselessleaf

Problem type

Fael has two strings, $S$ ~S~ and $T$ ~T~, and she wants to find all the possible results after she intertwines the strings. Intertwining two strings $S$ ~S~ and $T$ ~T~ is when all the characters of $S$ ~S~ and $T$ ~T~ are used to create a new string such that the order of the characters are preserved. For example, one possibility of intertwining ABC and DEF could be ABDECF.

Constraints

$1 \le |S|, |T| \le 12$ ~1 \le |S|, |T| \le 12~

$|X|$ ~|X|~ denotes the length of string $X$ ~X~.

Subtask 1 [10%]

$1 \le |S|, |T| \le 2$ ~1 \le |S|, |T| \le 2~

Subtask 2 [90%]

No additional constraints.

Input Specification

The first line of input contains two space-separated strings, $S$ ~S~ and $T$ ~T~.

Output Specification

Output every possible intertwined string on its own line. Order does not matter, but duplicates should not be printed.

Sample Input

AB CD

Sample Output

ABCD
ACBD
CABD
CADB
ACDB
CDAB

Comments

8

ayay9 commented on April 5, 2022, 12:41 a.m.

orz uselessleaf