PROBLEM STATEMENT
Rather than using the numeric digits 0 through 9 to compose numbers, letters of
the alphabet can be substituted for the digits. Simple addition problems can
then be represented as three words, the two addends and the total. For example,
FOUR+FIVE=NINE can represent the addition 2980+2674=5654 when R is 0, F is 2, E
is 4, N is 5, I is 6, V is 7, U is 8, and O (the letter O) is 9.
FOUR 2980 0123456789
+ FIVE + 2674 R_F_ENIVUO
------ ------
NINE 5654
Note that there is a one to one correspondence between the digits and letters.
One letter can represent exactly one digit, and one digit is represented by
exactly one letter.
Write a method that takes three strings as input representing two numbers, a
and b, and their sum. Return the largest possible value that the sum can take
when digits are substituted for the letters of a, b, and sum, so that the
following rules apply:
R1: No letter may represent more than one digit
R2: No digit may be represented by more than one letter
R3: Every letter in the arguments a, b, and sum must represent a unique digit
R4: After substituting digits for the letters of the arguments a, b, and sum,
the numbers which result must satisfy the equation Number(a) + Number(b) =
Number(sum). (See examples E8, E9, E10.)
R5: The digit '0' must not appear in the leading position of a, b, or sum,
unless there is only one position in a, b, or sum respectively.
If there is no result that can be produced that meets all of the criteria
outlined above, the method must return the special error value -1 (negative
one). Note that if more than 10 distinct letters appear in the aggregate total
of the letters used in a, b, and sum, the method must return -1 since there are
more letters than can be placed in one to one correspondence with the 10 digits
'0' through '9'. See example E7.
DEFINITION
Class: WordAdder
Method Name: maxTotal
Parameters: String,String,String
Returns: int
Method signature: int maxTotal(String a, String b, String sum)
(be sure your method is public)
TopCoder will ensure the validity of the inputs. Inputs are valid if all of
the following criteria are met:
* all arguments are from 1 to 9 characters in length inclusive
* all arguments consist of the uppercase letters 'A' through 'Z' inclusive
EXAMPLES
E1: "Z", "Z", "Z", ==> 0
E2: "Z", "A", "A", ==> 9
E3: "Z", "AZ", "AZ" ==> 90
E4: "ZZ", "AA", "AA" ==> -1
E5: "ABC", "DEF", "HI" ==> -1
E6: "AB", "CD", "EFGH" ==> -1
E7: "IJK", "ABCD", "EFGH" ==> -1
E8: "AA", "AA", "BB" ==> 88 // 44+44=88
E9: "AB", "CD", "EF" ==> 98 // 75+23=98
E10: "AB", "CD", "EFG" ==> 176 // 94+82=176
E11: "AAA", "BCD", "EFG" ==> 987
E12: "FOUR","FIVE","NINE" ==> 5654
E13: "ABCDEF","DGHIJD","JHGAAB" ==> 840773
E14: "CHOGY","TIM","CHEEE" ==> 98777
E15: "ABCDEFGHE","ABCDEFGHE","BDFIACEGJ" ==> 246913570