Problem Statement
- Next: Choose a lowercase character and replace its every occurrence with the next character. The next character of 'z' is 'a' ('a' -> 'b', 'b' -> 'c', ..., 'y' -> 'z', 'z' -> 'a').
- Prev: Choose a lowercase character and replace its every occurrence with the previous character. The previous character of 'a' is 'z' ('a' -> 'z', 'b' -> 'a', ..., 'y' -> 'x', 'z' -> 'y').
Definition
- Class:
- NextAndPrev
- Method:
- getMinimum
- Parameters:
- int, int, String, String
- Returns:
- int
- Method signature:
- int getMinimum(int nextCost, int prevCost, String start, String goal)
- (be sure your method is public)
Constraints
- nextCost and prevCost will each be between 1 and 1000, inclusive.
- start and goal will each contain between 1 and 50 characters, inclusive.
- start and goal will contain the same number of characters.
- Each character in start and goal will be a lowercase character.
Examples
5
8
"aeaae"
"bcbbc"
Returns: 21
There are several optimal sequences of operations. Here is one of them: "aeaae" -(Next)-> "bebbe" -(Prev)-> "bdbbd" -(Prev)-> "bcbbc". The total cost is 5 + 8 + 8 = 21.
5
8
"aeaae"
"bccbc"
Returns: -1
It is impossible to transform "aeaae" into "bccbc".
1
1
"srm"
"srm"
Returns: 0
start and goal may be the same. The cost of an empty sequence of operations is 0.
1000
39
"a"
"b"
Returns: 975
123
456
"pqrs"
"abab"
Returns: -1
100
19
"topcoder"
"ssszsffs"
Returns: 676
1
1000
"csk"
"wog"
Returns: 64
7
6
"qwerty"
"jjjjjj"
Returns: 125
1000
1000
"abcdefghijklmnopqrstuvwxyz"
"abcdefghijklmnopqrstuvwyxz"
Returns: -1
1000
1000
"abcdefghijklmnopqrstuvwxy"
"nopqrstuvwxyzabcdefghijkl"
Returns: 325000
150
328
"abcdefghijklmnopqrstuvwxyz"
"abcdefghijklmnopqrstuvwxyz"
Returns: 0
150
328
"tkjrdvuhggaovymbpawncstuqrfxlxdvciksxvpmqtpfbwezms"
"tkjrdvuhggaovymbpawncstuqrfxlxdvciksxvpmqtpfbwezms"
Returns: 0
150
328
"abcdefghijklmnopqrstuvwxpz"
"abcdefghijklmnopqrstuvwxpz"
Returns: 0
639
225
"abcdefghijklmnopqrstuvwxyz"
"tuvwxyzabcdefghijklmnopqrs"
Returns: -1
639
225
"zpxvahrqrpoxnoogkmnedoufhjovoicyqwbqwqgkswesslvtje"
"siqotakjkihqghhzdfgxwhnyachohbvrjpujpjzdlpxlleomcx"
Returns: -1
639
225
"abcdefgfijklmnopqrstuvwxyz"
"tuvwxyzybcdefghijklmnopqrs"
Returns: 39375
945
376
"abcdefghijklmnopqrstuvwxyz"
"bcdefghijklmnopqrstuvwxyza"
Returns: -1
586
386
"abcdefghijklmnopqrstuvwxyz"
"zabcdefghijklmnopqrstuvwxy"
Returns: -1
946
188
"cdefgjlmprswzz"
"fhjlqrstuxybcd"
Returns: -1
628
955
"rzsvlpkjzvktksgzzeohqkmxoowudidswbrztaxpofdzrchwis"
"wfxaruqpfaqyqxmfektnvqsdttbzjojxbhwfygdutljfwinbox"
Returns: -1
386
126
"ensxonexrlgcwufrzbtrgmxjuxqxo"
"xzllxsderbwadcvvppimtxtdtkffv"
Returns: -1
641
879
"cllcwwcipczzijccijlzwpeuwzijcyjcyqiqiziiwqueiceuzi"
"irrapzakiinnfcttfcrnziuxpnlcascisbkbknlfpbxufiuxnf"
Returns: -1
149
327
"p"
"p"
Returns: 0
208
156
"c"
"k"
Returns: 1664
208
52
"a"
"j"
Returns: 884
162
47
"fp"
"kk"
Returns: 987
163
69
"sf"
"yy"
Returns: 1380
31
26
"xi"
"bb"
Returns: 306
33
33
"vh"
"bb"
Returns: 396
48
110
"wh"
"aa"
Returns: 912
43
92
"oa"
"tt"
Returns: 817
55
654
"jgjhgjggjhhghghhggjjgjjhhjgjjghgggjhgj"
"rzrqzrzzrqqzqzqqzzrrzrrqqrzrrzqzzzrqzr"
Returns: 4840
21
537
"gjjmmjmgggmjmgmjgmjgggjggjm"
"qrryyryqqqyryqyrqyrqqqrqqry"
Returns: 630
99
659
"rum"
"yul"
Returns: -1
953
431
"tdltlddddldd"
"ixvivxxxxvxx"
Returns: -1
131
905
"pow"
"xxx"
Returns: 1179
115
579
"wrjs"
"tttt"
Returns: 2645
506
571
"wgnmz"
"nnnnn"
Returns: 8602
809
822
"zqeki"
"lllll"
Returns: 13818
713
595
"nnoxoxvunxvxvxouxvngugnunuonnnnxgnvgvggvougvvnugvo"
"vvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvv"
Returns: 11885
203
636
"iwidrydwywyyfhyhwwrhifhfdhrr"
"oooooooooooooooooooooooooooo"
Returns: 4669
535
202
"goigibbmsgbemgselbi"
"ttttttttttttttttttt"
Returns: 4777
262
727
"hzrjwyvcm"
"vvvvvvvvv"
Returns: 6550
792
9
"qfrxtvdney"
"eeeeeeeeee"
Returns: 225
859
516
"bfgivwecyxt"
"qqqqqqqqqqq"
Returns: 9288
33
544
"yrbqvprbyqqyjgpjponpmvyqxxmbjopooyyrbojmrqb"
"qqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqq"
Returns: 825
839
221
"rycdcedrfthrsytscitwkcwdyyhcrkysnk"
"uuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuu"
Returns: 5525
58
788
"qlrpvafecikbyw"
"hhhhhhhhhhhhhh"
Returns: 1450
853
816
"tfkquivrobhzejx"
"ccccccccccccccc"
Returns: 18470
542
513
"yvajquixntmwspdf"
"wwwwwwwwwwwwwwww"
Returns: 12089
845
169
"aetiycjgphnlkwmbz"
"wwwwwwwwwwwwwwwww"
Returns: 3887
710
235
"nkvxexpekkqakpkbtxrcixadmyjidciv"
"gggggggggggggggggggggggggggggggg"
Returns: 5640
920
697
"yuecwtktrzaykzhntqbwgwncavhdytpnhzh"
"ooooooooooooooooooooooooooooooooooo"
Returns: 16254
413
791
"usjgricbktfypdnvmoq"
"sssssssssssssssssss"
Returns: 10325
838
333
"zhgvaqqdyjpbwfobwiyguboxxuiecn"
"iiiiiiiiiiiiiiiiiiiiiiiiiiiiii"
Returns: 8325
163
607
"oagnoyjhpmlcidbvkrzgfeu"
"qqqqqqqqqqqqqqqqqqqqqqq"
Returns: 4075
957
593
"vbmyytaqhcwxojfzlsjpvgngrk"
"mmmmmmmmmmmmmmmmmmmmmmmmmm"
Returns: 14825
236
930
"wdfzzgaitahicmgygfosxupptnvklavibumzsmnhq"
"sssssssssssssssssssssssssssssssssssssssss"
Returns: 5900
817
563
"gdetvrqmzfcbphksaoywjuix"
"vvvvvvvvvvvvvvvvvvvvvvvv"
Returns: 14075
650
324
"japmxdteywgbrclvhosqkzuin"
"uuuuuuuuuuuuuuuuuuuuuuuuu"
Returns: 8100
480
741
"ncfvctvmuorurzhgkycjfkojmkwpzxdwpqslwynaseibgy"
"yyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyy"
Returns: 12000
270
871
"qhaefvcryidtzkxjgupwsnmbol"
"yyyyyyyyyyyyyyyyyyyyyyyyyy"
Returns: 6750
605
450
"adylkxevgojpizrqjbmfut"
"wwwwwwwwowowwwwwowwoww"
Returns: -1
25
646
"jwrjuayhcrcltsgtzhdfcbtliwjhvqramzowxxdnpev"
"bbsbsbbbbsbbssbsbbbbbbsbbbbbsssbsbsbbbbssbs"
Returns: 1575
734
392
"ebduxmgofrzayqlph"
"kkkkkddddkkkkdddd"
Returns: 12936
643
60
"tkektrrekuajieurxjxaeiehhkcea"
"sssssjjssssssssjsssssssssssss"
Returns: 1560
816
133
"yycwzwjupzfuufwefvvowbecuudpe"
"ggogggbbbgcbbcgbcggbggbobbobb"
Returns: -1
965
973
"xyjsicbmoprgflppcniarepjscijdstdarixflxtkijqsm"
"bbfbfcbbbbbffbbbcbfbbfbfbcfffbbfbbfbfbbbbffbbb"
Returns: 22227
47
705
"yqx"
"esb"
Returns: 564
689
453
"ehozkgqyacbdpnmltfvirjs"
"bkkrkkkrrrrrkkkkrbrkrkr"
Returns: 12722
967
1
"sohzujeigusdhuxptwaoqpsntwzbrfcbtyszwlk"
"mbbbmcbbbmmbbmmmmmbbmmmcmmbbmbbbmbmbmcc"
Returns: -1
5
765
"rbccjcbccrcbbjcbrccccjjbccjrbjcjccbb"
"jwddfdwddjdwwfdwjddddffwddfjwfdfddww"
Returns: 440
783
522
"dohvrincximapfqgzb"
"jwuhwuwjjuwjwjwjjj"
Returns: 36801
143
932
"qtaforg"
"wwccqwg"
Returns: 4226
506
113
"farreafpftdolloizikpzjetrdrjatedproad"
"jbqqjbjqjqhpkkpjbjjqbjjqqhqjbqjhqqpbh"
Returns: 7143
146
743
"zbmagsqwvoxue"
"hhthivvxvthvi"
Returns: 3942
512
913
"fadoafagfeugslgsjnffxhisizenzdlyoqtgiqxzzstzp"
"hzzyzhzhhhzhzyhzmyhhzjjzjzhyzzyzyyzhjyzzzzzzy"
Returns: 17988
123
555
"glenqo"
"fgbgxi"
Returns: 10296
53
851
"xspvciwarh"
"qgfjrwgqfr"
Returns: -1
923
416
"wcvpdyflsemluguoibjnrtx"
"ekeelklrelrreleuqkqueek"
Returns: 48672
97
553
"napyjrogryqngdmjwcwxuisgjeyxgskqhmkcq"
"xnyknyxnykyxnnwnknkkknfnnnkknfnynwnny"
Returns: 6887
616
952
"onbzdwateuxsmjv"
"dzwpwnwmwmpdzzn"
Returns: 60928
588
487
"ukzksqepyywiqucmccvikoygemgyowo"
"odpdmhyhppoyhordrroydhpvydvphoh"
Returns: -1
156
669
"baygmljozhnucteqrisdkfvw"
"vvvhnkhnvhnnvnbnnhnvkfpv"
Returns: 18375
648
471
"peoysdtgkzurni"
"sqslwpeqqpfwqq"
Returns: 46656
874
118
"wprvusdyrszdakpowsuvynda"
"jzzjccqnzcqqqxzyjccjnyqq"
Returns: 12036
818
116
"kqzxxzcejidiycyllqkldwrxidgbzwbcdbnlgil"
"pnnttnpqbtqttptggnpgqgnttqtpngppqpbgttg"
Returns: -1
632
653
"tykadvomigebhxzj"
"ijaowiidaaztaioa"
Returns: 52893
36
716
"ojbkngxlrucdmuwb"
"qmfmqmdoycfkocdf"
Returns: 1620
552
249
"thqvzakpgejcwdxnyso"
"jxijuuyixwxujwqdqii"
Returns: 20169
750
720
"mnlsvrhyikqsobmzxmiunohjshgyb"
"kmcmmmfvfgmmmxkxtkfmmmfzmfcvx"
Returns: -1
401
581
"cbgfnefukhztdriayxwmbkqsvljaxop"
"bbjjwjjyukbygyrbbbbubuxyyuubbwx"
Returns: 24641
847
387
"ikknmnzwzzzxnqnplylpzlignuznyxnikgmgyuupwxyxqzymxi"
"tuuzxzqnqqqpzkzdwpwdqwttzlqzppztutxtplldnpppkqpxpt"
Returns: 49923
16
780
"elwgzszemaszgnzggbjehtjabstlkffjessonpwu"
"iwfkfafiwfafkxfkkfwisbwffabwwjjwiaayxzfc"
Returns: 1584
184
840
"kjvfdtpxyerzgabwhoqnulcsmi"
"ppdnnxuugngmommfowtvytnxup"
Returns: -1
49
729
"fwegakhlivdsypqtrubxm"
"vwhoumjmdvgsyoquruvwm"
Returns: -1
833
399
"pyemqgtkzfndhrjxvswauio"
"vimtvndrimykoyqigcpjfph"
Returns: -1
576
426
"ayhdcrtgpbmjzqvolufni"
"jhrolaaqyktshzgwtbpur"
Returns: 88704
811
410
"xoiwzgqblkujmerdafyvthsc"
"ewpegoyhsrcqtkzigmgdboah"
Returns: 112729
614
128
"ekqtypivfcrhlsloanucxgmiaz"
"jcvydlnbviwmjxjthruieabnhw"
Returns: -1
393
645
"zndjbgvlfcqhsauyoxeimwrkpt"
"wjafycrhczmdoxqvkubeitnglp"
Returns: 58695
306
26
"me"
"ii"
Returns: 572
1
1
"abcdefghijklmnopqrstuvwxyz"
"zabcdefghijklmnopqrstuvwxy"
Returns: -1