Problem Statement
A lattice crossword is a variant of a crossword where exactly 4 words are arranged in the form of a lattice (like a '#' sign). Given 4 words, a, b, c and d, return the number of different lattice crosswords that can be created according to the following rules:
- Each of the four given words must appear in the crossword exactly once.
- Two of the four words must be printed horizontally, from left to right.
- Two of the four words must be printed vertically, from top to bottom.
- Each horizontal word must cross both vertical words (each through exactly one common letter).
- Each vertical word must cross both horizontal words (each through exactly one letter).
- The horizontal words must be separated by at least one row.
- The vertical words must be separated by at least one column.
Two lattice crosswords are considered different if at least one of the words is at a different position. The position of a word is determined by the row and column position of its first letter. Row 0 is the row of the topmost letter in the crossword, and column 0 is the column of the leftmost letter in the crossword.
c
o
p n
r t
topcoder
b s
solution
e
m
Here the leftmost letter is "t" of the "topcoder" and the topmost letter is "c" of the "contest".
So, the positions of the words are:
"topcoder" - (0, 4)
"contest" - (6, 0)
"problem" - (4, 2)
"solution" - (2, 6)
Another one lattice crossword, which can be constructed using this words is:
t
o
p s
c o
problem
d u
contest
e i
o
n
Definition
- Class:
- LatticeCrossword
- Method:
- crossword
- Parameters:
- String, String, String, String
- Returns:
- int
- Method signature:
- int crossword(String a, String b, String c, String d)
- (be sure your method is public)
Constraints
- a, b, c and d will each contain between 3 and 15 characters, inclusive.
- a, b, c and d will be distinct.
- a, b, c and d will contain only lowercase letters ('a'-'z').
Examples
"topcoder"
"contest"
"problem"
"solution"
Returns: 2
Example from the problem statement.
"coder"
"number"
"rober"
"joker"
Returns: 0
No lattice crossword can be constructed.
"lattice"
"crossword"
"disticnt"
"approach"
Returns: 4
"zaxb"
"axc"
"cxd"
"bxdy"
Returns: 2
Two lattice crosswords: z zaxb axc x x and x x cxd bxdy y
"aaaaaaaaaaaaaaa"
"aaaaaaaaaaaaba"
"aaaaaaaaaaaaaab"
"baaaaaaaaaaaaaa"
Returns: 10082176
A lot of crosswords.
"aaaaaaaaaaaaaaa"
"aaabaaaaaaaaaab"
"aaaaaabaaaabaaa"
"abaaaaabaaaaaaa"
Returns: 6981150
"aaaaaaaaaaaaaaa"
"aaaaaaaaaaaaaa"
"aaaaaaaaaaaaa"
"aaaaaaaaaaaa"
Returns: 7605840
"aaaaaaabbbbbbbb"
"aaaaaaaabbbbbbb"
"bbbbbbbbaaaaaaa"
"bbbbbbbaaaaaaaa"
Returns: 1376112
"kil"
"kjnoi"
"llm"
"jlii"
Returns: 0
"oiomjo"
"iijll"
"hnimjj"
"ioi"
Returns: 2
"ikoni"
"mlio"
"hkimh"
"imihml"
Returns: 2
"jij"
"lonl"
"lkohmh"
"kioih"
Returns: 0
"koom"
"oni"
"hihh"
"mhh"
Returns: 2
"jnolh"
"inkhhi"
"mjnj"
"hnj"
Returns: 0
"hjl"
"moo"
"mlmkl"
"imhlik"
Returns: 0
"omo"
"moi"
"nkom"
"ihjlh"
Returns: 0
"ojmkk"
"ljmhn"
"kmmno"
"liooji"
Returns: 0
"khh"
"lhkm"
"iljjik"
"ijm"
Returns: 0
"ihkn"
"iojhn"
"mkjih"
"hiohjh"
Returns: 2
"jooiil"
"jmom"
"hhk"
"jhjhl"
Returns: 0
"jjlhh"
"ioo"
"hon"
"nmi"
Returns: 0
"oilkn"
"momhj"
"omkj"
"oinn"
Returns: 0
"oojh"
"mil"
"nooij"
"nni"
Returns: 0
"mill"
"mjhnkl"
"hjkjkn"
"jjn"
Returns: 0
"oik"
"immi"
"homkk"
"inlonk"
Returns: 0
"ohnhoi"
"oomn"
"jhnnj"
"khmi"
Returns: 0
"jio"
"jlllko"
"nnkim"
"mjkon"
Returns: 0
"lonnin"
"nnkkl"
"hjnhoi"
"lmkn"
Returns: 0
"dbacdccdba"
"abbcabbddb"
"bcdcbbcaadacb"
"ccabdbcbddc"
Returns: 7298
"bbabdcadbba"
"bbbabaacbcbad"
"adaddabacdbd"
"abdddbadcbb"
Returns: 14872
"baaabaaccc"
"aadbcdaabbbcc"
"aaccaacaabdd"
"babdadbbaabd"
Returns: 15222
"dbdabdbbcd"
"bcbacaacdcbdd"
"acbaccdbbcdd"
"bddcbadaab"
Returns: 7676
"adbdbaccbd"
"bcbbbadccb"
"caccbdcbadabd"
"cadcddbbab"
Returns: 6608
"bdbaaadccaca"
"cccaaaabdd"
"adcacbbcdb"
"dccbdbacbd"
Returns: 5064
"dcbdbccbddc"
"abbaccddbc"
"ccbbbbaadb"
"acdadacdcdca"
Returns: 5102
"ccadbdbbbbbc"
"dbdddbcadc"
"ddacadbbddbcc"
"acccbdabbacb"
Returns: 12202
"dcaaaddcccdbb"
"bcddcdadccbc"
"ccddadaccadb"
"abdcaacbdda"
Returns: 17834
"baababdccdcab"
"bbaabbdccca"
"aacddcbcab"
"ccdacbdcbc"
Returns: 7604
"dbdccbadccdba"
"dbcbdbbbbdad"
"bcbabddaacb"
"dbabcabbadaa"
Returns: 13972
"cbaaccbcbbdac"
"dddddadaacd"
"aadadcbcbabbb"
"daacbabdadda"
Returns: 10156
"cdacbaddabba"
"ccdbbcadcba"
"abdadcdddc"
"dcddbbcaccbca"
Returns: 8860
"adcbddaddccc"
"cdddcabcccda"
"bcddcdbbac"
"cbdcccaadbdd"
Returns: 14794
"bbccaddcabd"
"daccbaaaccd"
"abdcbdccbdcbd"
"dacdbcccbccd"
Returns: 13130
"cadbbdcccbaad"
"ccacdadbaba"
"aabdacaccdaac"
"acbccbccdcdc"
Returns: 19098
"bbdadcccdcbcb"
"ddccaaddcdaab"
"cbcaabaccbcc"
"baabdadcbaccb"
Returns: 19148
"accbbdbccdb"
"cdacbcbdbbcc"
"adccddddad"
"daddabdcadd"
Returns: 7068
"dbdcdccacda"
"ddbbccacbcacd"
"bbdbcdaacbadb"
"bdbbdcabdd"
Returns: 10094
"cdbdbdadbacca"
"cdabbcbabbbad"
"bdadcbaacacdd"
"bcacdaabdcdab"
Returns: 22428
"ntwozeifzs"
"qxfsexbvtr"
"pelibvqucvsqd"
"qeudfraprbq"
Returns: 6
"hrkhdyclljw"
"vtfolykydunsl"
"inmxlurmqdnd"
"sjpjpxczejh"
Returns: 2
"howotgwqgc"
"iwrvyzgmdtnyc"
"qwmgsyecirlj"
"tgddczpvqkvb"
Returns: 10
"hjxixtzhoh"
"bmresimwxuvld"
"gmzygajbdyxt"
"tjnglyvsej"
Returns: 2
"efdbnwyklf"
"tsxvtqxgkh"
"qquurduvwjyfl"
"ysronhrjen"
Returns: 2
"pfpsauhquqsc"
"qmocqkorzn"
"qfqmcnpgtf"
"xesffvwixd"
Returns: 0
"ruddxeaxvfy"
"qrjeaiftlc"
"gefbhpyehn"
"ekfyvsizuzoy"
Returns: 0
"uuedzbthrxty"
"jdlzvbiclc"
"zfgamtdjpvlas"
"mygevfohhucb"
Returns: 2
"nymquxdwssvrj"
"zktpwrujuonq"
"owtbabkkainb"
"srpomwqhtfo"
Returns: 2
"fqorornsclasr"
"nfokpjpuguy"
"cimplczagl"
"cqnacdpyty"
Returns: 8
"hjjwylybsqnhe"
"jlmxbdbjbzon"
"dcdqhtlusov"
"pfojccjbohgm"
Returns: 20
"qhymcehmntruo"
"dzzlnspcyub"
"kefgzcruzirrb"
"zguutelrcpvg"
Returns: 12
"qlkgjudbilbg"
"mezvdqklczg"
"ixrwlulvlc"
"bmffttwikmnws"
Returns: 0
"ebupbnghxuyi"
"kvdnqsxcgkjy"
"xybnqpbbum"
"sbxyaqiydrvp"
Returns: 18
"thweifbispf"
"tmyozkqccib"
"sdlaztayxdwjn"
"hgkbnqssrmkp"
Returns: 2
"agfjfricihoar"
"aaqkpahlctk"
"oqfbcgaqatkug"
"iwvwohkihupg"
Returns: 28
"dtbehqymzunop"
"bfqmywtxidqqx"
"oliomlmschkw"
"bskbzczgtmiaj"
Returns: 4
"kaudfxlmwlf"
"cnmqjwlvdjkg"
"sxscbxxpez"
"bevzindkqrd"
Returns: 4
"zflkdgcysbc"
"tvdpyegshigkt"
"phnhixyqyjuff"
"vvxvfccbfd"
Returns: 8
"gfnjfzunnigsc"
"ubepjglqxtjwn"
"blynybucyqcdl"
"jiywrauxzafgx"
Returns: 12
"xxxxxxxxxxxxx"
"yyyyyyyyyyyyy"
"yxyxyxyxyxyxy"
"xyxyxyxyxyxyx"
Returns: 222640
"aaaaaa"
"bbbbbb"
"ccc"
"ddddddd"
Returns: 0
"aaacaaaaaacaaaa"
"aaacaaaaaaaacaa"
"aacaaaaaaacaaca"
"acaacaaaacaaaaa"
Returns: 4336114
"bbaabaabbaaabba"
"bbbbbbbababbaaa"
"aabbaaabbbabbba"
"bbabbaabbbabbbb"
Returns: 1083428
"baaabababaababb"
"baabbbbabbbbbab"
"bbabaaabaaaaaba"
"bbabaabbbaaaaaa"
Returns: 858336
"aaaaabbbababbab"
"baabbabbbabbbba"
"bbabaaaaababbba"
"abaaabbbabbabbb"
Returns: 997616
"babaabaabbbbaaa"
"bababbbabaabbaa"
"abbabababbaaaba"
"bbbababbbaaabaa"
Returns: 996664
"aabaaaaaaaaaaaa"
"baaaaaaaaaaaaaa"
"aaaaaaaaaaaabaa"
"aaaaaaaaaaaaaaa"
Returns: 11115316
"bbaabaabbaaabb"
"abbbbbbb"
"babbaaa"
"aabbaaabbba"
Returns: 35462
"bbabb"
"abbaabb"
"abbbbabaaaba"
"aba"
Returns: 308
"babbabaabbb"
"abbbbbababbab"
"aaba"
"aaabaabbabaa"
Returns: 13558
"bbaaaa"
"aaaaaaabbbab"
"bbabbbaab"
"abbb"
Returns: 2816
"bbbbabbbaba"
"aaababbb"
"aabaaabb"
"abbabb"
Returns: 10548
"abc"
"cba"
"acb"
"bca"
Returns: 2
"aaaaabbbbb"
"bbbbbaacc"
"aaadddccc"
"eeedddaaacccc"
Returns: 2060
"abc"
"aab"
"ccc"
"bcc"
Returns: 2
"aggbbaaabcaapao"
"abbcrgcaabcau"
"cbbwaaabbabee"
"abbaaaeaabaaij"
Returns: 26306