Problem Statement
All strings in this problem are strings of lowercase English letters ('a'-'z') only.
A string X is called a substring of a string Y if the characters of X appear as a contiguous subsequence somewhere in Y. For example, "bc" is a substring of "abcde" but "bd" and "ca" are not.
If X is a substring of Y, Y is called a superstring of X.
You are given three
A string D is called a common superstring of A, B and C if it's a superstring of each of them.
For example, if A = "pq", B = "qrr", and C = "rsp": The string "pqrrsp" is their common superstring. The string "xpqxrspxqrrx" is also their common superstring. The string "rspyqrr" is not their common superstring, because it doesn't contain the string A.
Your task is to find and return all possible shortest superstrings of A, B and C. More precisely:
- Find the smallest possible length L the common superstring may have.
- Find all superstrings of that length L.
- Return a
String[] containing all those strings. The returned array must be sorted in ascending order.
Definition
- Class:
- ShortShortSuperstring
- Method:
- constructAll
- Parameters:
- String, String, String
- Returns:
- String[]
- Method signature:
- String[] constructAll(String A, String B, String C)
- (be sure your method is public)
Constraints
- A will contain between 1 and 5 characters, inclusive.
- B will contain between 1 and 5 characters, inclusive.
- C will contain between 1 and 5 characters, inclusive.
- Each character in A + B + C will be a lowercase English letter ('a'-'z').
Examples
"ab"
"ef"
"cd"
Returns: {"abcdef", "abefcd", "cdabef", "cdefab", "efabcd", "efcdab" }
There is no D with fewer than six characters. The best D has therefore exactly six characters. There are six such strings. Note that they have to be returned in sorted order.
"a"
"aaa"
"aa"
Returns: {"aaa" }
The string "aaa" is a superstring of "a", "aaa", and "aa". It's clearly the shortest possible superstring of all three given strings, and it's also clear that it's unique.
"aaa"
"aaa"
"aaa"
Returns: {"aaa" }
The strings A, B and C are not necessarily distinct.
"aab"
"aaaa"
"caa"
Returns: {"caaaab" }
"hello"
"oxbow"
"watch"
Returns: {"helloxbowatch", "oxbowatchello", "watchelloxbow" }
"hello"
"locow"
"watch"
Returns: {"hellocowatch", "watchellocow" }
"qwert"
"asdfg"
"zxcvb"
Returns: {"asdfgqwertzxcvb", "asdfgzxcvbqwert", "qwertasdfgzxcvb", "qwertzxcvbasdfg", "zxcvbasdfgqwert", "zxcvbqwertasdfg" }
"y"
"y"
"y"
Returns: {"y" }
"y"
"y"
"z"
Returns: {"yz", "zy" }
"y"
"z"
"y"
Returns: {"yz", "zy" }
"z"
"y"
"y"
Returns: {"yz", "zy" }
"lllll"
"llll"
"l"
Returns: {"lllll" }
"aaiia"
"ai"
"ii"
Returns: {"aaiia" }
"s"
"ldsds"
"dsd"
Returns: {"ldsds" }
"i"
"lilir"
"i"
Returns: {"lilir" }
"zp"
"zrzz"
"rq"
Returns: {"rqzrzzp", "zrzzprq" }
"dy"
"ygdgd"
"yg"
Returns: {"dygdgd", "ygdgdy" }
"f"
"a"
"c"
Returns: {"acf", "afc", "caf", "cfa", "fac", "fca" }
"ujrr"
"truy"
"tujr"
Returns: {"truytujrr", "tujrrtruy" }
"hh"
"h"
"yhhpl"
Returns: {"yhhpl" }
"rqts"
"r"
"qtdcc"
Returns: {"qtdccrqts", "rqtsqtdcc" }
"ommv"
"omm"
"o"
Returns: {"ommv" }
"iwhii"
"iwhii"
"iwhi"
Returns: {"iwhii" }
"hnfn"
"n"
"ozqt"
Returns: {"hnfnozqt", "ozqthnfn" }
"grt"
"ygp"
"x"
Returns: {"grtxygp", "grtygpx", "xgrtygp", "xygpgrt", "ygpgrtx", "ygpxgrt" }
"gr"
"xrtgr"
"r"
Returns: {"xrtgr" }
"lhh"
"h"
"hhrnp"
Returns: {"lhhrnp" }
"qucg"
"c"
"qucg"
Returns: {"qucg" }
"tr"
"pdfyd"
"qcq"
Returns: {"pdfydqcqtr", "pdfydtrqcq", "qcqpdfydtr", "qcqtrpdfyd", "trpdfydqcq", "trqcqpdfyd" }
"sa"
"nt"
"ntin"
Returns: {"ntinsa", "santin" }
"hgdgz"
"xyug"
"gd"
Returns: {"hgdgzxyug", "xyughgdgz" }
"iiii"
"iiiii"
"iiii"
Returns: {"iiiii" }
"aaaa"
"sssa"
"aaaa"
Returns: {"sssaaaa" }
"dded"
"edde"
"dedda"
Returns: {"eddedda" }
"poouz"
"ouzoo"
"ooopp"
Returns: {"poouzooopp" }
"vybds"
"bydvv"
"ydvvy"
Returns: {"bydvvybds" }
"ngvk"
"ngvkn"
"vknn"
Returns: {"ngvknn" }
"bmtpp"
"mtpp"
"bmtp"
Returns: {"bmtpp" }
"gqigs"
"zgqig"
"gqig"
Returns: {"zgqigs" }
"oedd"
"ddii"
"yedo"
Returns: {"yedoeddii" }
"cjjcx"
"jcxz"
"cxzjj"
Returns: {"cjjcxzjj" }
"ii"
"ii"
"i"
Returns: {"ii" }
"v"
"vv"
"vv"
Returns: {"vv" }
"t"
"st"
"t"
Returns: {"st" }
"tj"
"j"
"j"
Returns: {"tj" }
"m"
"m"
"mm"
Returns: {"mm" }
"a"
"jl"
"a"
Returns: {"ajl", "jla" }
"r"
"o"
"ro"
Returns: {"ro" }
"p"
"vq"
"rp"
Returns: {"rpvq", "vqrp" }
"k"
"k"
"y"
Returns: {"ky", "yk" }
"rd"
"r"
"c"
Returns: {"crd", "rdc" }
"jjj"
"jj"
"jj"
Returns: {"jjj" }
"o"
"og"
"gg"
Returns: {"ogg" }
"tktk"
"k"
"gt"
Returns: {"gtktk" }
"jh"
"hhph"
"p"
Returns: {"jhhph" }
"qq"
"mnnqq"
"msqss"
Returns: {"mnnqqmsqss", "msqssmnnqq" }
"md"
"cdn"
"cnxm"
Returns: {"cdncnxmd", "cnxmdcdn" }
"vif"
"vvth"
"cti"
Returns: {"ctivifvvth", "ctivvthvif", "vifctivvth", "vifvvthcti", "vvthctivif", "vvthvifcti" }
"dvdh"
"qh"
"fpd"
Returns: {"fpdvdhqh", "qhfpdvdh" }
"cef"
"wic"
"mi"
Returns: {"miwicef", "wicefmi" }
"a"
"njd"
"jl"
Returns: {"ajlnjd", "anjdjl", "jlanjd", "jlnjda", "njdajl", "njdjla" }
"gs"
"gau"
"hhgr"
Returns: {"gaugshhgr", "gauhhgrgs", "gsgauhhgr", "gshhgrgau", "hhgrgaugs", "hhgrgsgau" }
"sy"
"qc"
"c"
Returns: {"qcsy", "syqc" }
"bmmu"
"ukuqj"
"qhdps"
Returns: {"bmmukuqjqhdps", "qhdpsbmmukuqj" }
"mvv"
"fjqml"
"ej"
Returns: {"ejfjqmlmvv", "ejmvvfjqml", "fjqmlejmvv", "fjqmlmvvej", "mvvejfjqml", "mvvfjqmlej" }
"eip"
"bhr"
"rmc"
Returns: {"bhrmceip", "eipbhrmc" }
"whtwa"
"ikti"
"ma"
Returns: {"iktimawhtwa", "iktiwhtwama", "maiktiwhtwa", "mawhtwaikti", "whtwaiktima", "whtwamaikti" }
"whmf"
"hnxxx"
"evwvx"
Returns: {"evwvxhnxxxwhmf", "evwvxwhmfhnxxx", "hnxxxevwvxwhmf", "hnxxxwhmfevwvx", "whmfevwvxhnxxx", "whmfhnxxxevwvx" }
"x"
"jro"
"e"
Returns: {"ejrox", "exjro", "jroex", "jroxe", "xejro", "xjroe" }
"cg"
"egeig"
"mig"
Returns: {"cgegeigmig", "cgmigegeig", "egeigcgmig", "egeigmigcg", "migcgegeig", "migegeigcg" }
"ef"
"sywo"
"s"
Returns: {"efsywo", "sywoef" }
"fffff"
"ffff"
"ffff"
Returns: {"fffff" }
"hhlhh"
"llll"
"llhh"
Returns: {"llllhhlhh" }
"gtttg"
"tatg"
"atgt"
Returns: {"tatgtttg" }
"ttdw"
"dtwtw"
"twkdk"
Returns: {"dtwtwkdkttdw", "ttdwdtwtwkdk" }
"cphhp"
"dphdd"
"dchdh"
Returns: {"cphhpdphddchdh", "dphddchdhcphhp" }
"rqpoo"
"rkrpr"
"qkoo"
Returns: {"qkoorkrprqpoo", "rkrprqpooqkoo" }
"ihbb"
"whhg"
"ssiu"
Returns: {"ihbbssiuwhhg", "ihbbwhhgssiu", "ssiuihbbwhhg", "ssiuwhhgihbb", "whhgihbbssiu", "whhgssiuihbb" }
"dfkka"
"imkmi"
"imdif"
Returns: {"dfkkaimkmimdif", "imkmimdifdfkka" }
"xrrrt"
"lcul"
"extlo"
Returns: {"extlolculxrrrt", "extloxrrrtlcul", "lculextloxrrrt", "lculxrrrtextlo", "xrrrtextlolcul", "xrrrtlculextlo" }
"kgge"
"lxeex"
"rrgz"
Returns: {"kggelxeexrrgz", "kggerrgzlxeex", "lxeexkggerrgz", "lxeexrrgzkgge", "rrgzkggelxeex", "rrgzlxeexkgge" }
"tt"
"t"
"t"
Returns: {"tt" }
"bb"
"b"
"aa"
Returns: {"aabb", "bbaa" }
"z"
"nx"
"x"
Returns: {"nxz", "znx" }
"af"
"nn"
"ae"
Returns: {"aeafnn", "aennaf", "afaenn", "afnnae", "nnaeaf", "nnafae" }
"yx"
"q"
"y"
Returns: {"qyx", "yxq" }
"hr"
"t"
"lt"
Returns: {"hrlt", "lthr" }
"dd"
"bu"
"b"
Returns: {"budd", "ddbu" }
"al"
"k"
"fx"
Returns: {"alfxk", "alkfx", "fxalk", "fxkal", "kalfx", "kfxal" }
"bb"
"zq"
"w"
Returns: {"bbwzq", "bbzqw", "wbbzq", "wzqbb", "zqbbw", "zqwbb" }
"y"
"ts"
"h"
Returns: {"htsy", "hyts", "tshy", "tsyh", "yhts", "ytsh" }
"aaaaa"
"aaaaa"
"aaaaa"
Returns: {"aaaaa" }
"sssqq"
"ssqqq"
"ssssq"
Returns: {"ssssqqq" }
"mmiim"
"iimmm"
"miimm"
Returns: {"mmiimmm" }
"ywyyl"
"wyyll"
"yylli"
Returns: {"ywyylli" }
"mmtmm"
"tmmly"
"mtmml"
Returns: {"mmtmmly" }
"yvvff"
"vffvi"
"vvffv"
Returns: {"yvvffvi" }
"qrdld"
"dlddq"
"rdldd"
Returns: {"qrdlddq" }
"tkgck"
"kgckn"
"ctkgc"
Returns: {"ctkgckn" }
"bobcc"
"bccoc"
"obcco"
Returns: {"bobccoc" }
"yytfy"
"kyytf"
"gkyyt"
Returns: {"gkyytfy" }
"t"
"t"
"t"
Returns: {"t" }
"a"
"a"
"b"
Returns: {"ab", "ba" }
"w"
"h"
"u"
Returns: {"huw", "hwu", "uhw", "uwh", "whu", "wuh" }
"zz"
"zz"
"zz"
Returns: {"zz" }
"ww"
"pz"
"wp"
Returns: {"wwpz" }
"aj"
"ua"
"jg"
Returns: {"uajg" }
"aa"
"aab"
"aabc"
Returns: {"aabc" }
"abc"
"obell"
"bello"
Returns: {"abcobello", "obelloabc" }
"adcd"
"dc"
"y"
Returns: {"adcdy", "yadcd" }
"abc"
"cbe"
"cbe"
Returns: {"abcbe" }
"atc"
"tca"
"btca"
Returns: {"btcatc" }