Background
A matryoshka doll (or Russian nesting doll) is a set of dolls that fit inside of each other. I've accidentally mixed up my collection of matryoshka dolls and I don't remember which one goes inside which.
Objective
Given a list of unique strings, sort them into nested matryoshka dolls. Each string is an individual doll, and a matryoshka doll is a list of strings.
Rules
Let min(a,b)
be the lexicographic min of strings a
and b
. Let a ⊂ b
denote that a
is a substring of b
. Then,
- The list of matryoshka dolls must be sorted lexicographically
- String
a
can fit into stringb
ifa ⊂ b
- If
a ⊂ b
anda ⊂ c
, thena
will go insidemin(b,c)
- If both
a ⊂ c
andb ⊂ c
, buta ⊄ b
b ⊄ a
, then onlymin(a,b)
will go insidec
- If both
a ⊂ c
andb ⊂ c
, and alsoa ⊂ b
, then onlyb
will go insidec
. I.e., superstrings go before substrings so that the matryoshka isn't prematurely terminated.
Examples
In:
hahaha, hah, lol, lololol, bahaha, bah, haha, ah
Out:
bahaha, bah, ah
hahaha, haha, hah
lololol, lol
In:
aa, aaaa, a, aaaaaaaaaa
Out:
aaaaaaaaaa, aaaa, aa, a
ab, ba, aba, bab
? By rule 3, bothab
andba
should go intoaba
, and by rule 4,ba
cannot go into eitheraba
orbab
. \$\endgroup\$