Verbal Arithmetic Puzzle

The idea here is to use the backtracking with one condition, which is explicitly mentioned in the problem itself that each word will decode as one number with no leading zeros. We know that if a + b = c, then a + b - c = 0 is also correct. So this is another condition which we are going to use in this approach.

First, add the ‘RESULT’ string in the array of string ‘WORDS’. We are traversing the array ‘WORDS’ from right to left column-wise. At each position, we have to know the ‘SUM’ we have so far, and for this, we'll use a variable named 'BALANCE', and we want it to be exactly zero at the end of all columns. So, if the 'BALANCE' is zero at the end of all columns, then return “true” as we have successfully found a valid mapping of the letter to the digit. If we completed a column and 'BALANCE' % 10 is not 0, then return “false”. Else we have to search in another column with balance as 'BALANCE' / 10. Because when we subtract the result string, we want each column’s last value to be zero, which we get by using the % function and the remaining part we’ll send for the further steps in the form of a carry, which is nothing but the updated 'BALANCE'.

If we are at the letter for which there is a prior mapping to digit, then we are going to use this mapping if the mapping is not zero. If it is zero, then the word has to be of length one, or the column in which we are currently at is not to be the last for that letter. Else, we have to assign a new mapping and call the function again.

Steps:

1. Add 'RESULT' string into the array of string ‘WORDS’.
2. Create two variables, 'TOTALROWS', and 'TOTALCOLS'.
3. Initialize 'TOTALROWS' to the size of the array ‘WORDS and 'TOTALCOLS' to the size of the longest string in that array.
4. Create a HashMap named 'LETTODIG' which is used to store the mapping of the letter to the digit.
5. Create an array of data type char of size 10 named 'LETTODIG', which is used to find the current mapping of a particular digit to the letter. Initialize this array with the character ‘-’.
6. Call the function isAnyMapping(‘WORDS, ‘ROW’, ‘COL’, ‘BAL’, 'LETTODIG', ‘DIGTOLET’, 'TOTALROWS', 'TOTALCOLS'), where ‘WORDS is the array of the string, ‘ROW’, and ‘COL’ denote the (COL)-th char in the (ROW)-th word from right to left which is initially 0, bal is the current balance which is also initially 0.
7. isAnyMapping function will return “true” if there exists any possible mapping of the letters to the digits. Else it returns false.
8. Return the value which is returned by the above function.

bool isAnyMapping(string words[], int row, int col, int bal, HashMap letToDig, char digToLet[], int totalRows, int totalCols):

1. If ‘COL’ == 'TOTALCOLS'  and ‘BAL’ == 0, then return true. Else, return false.
2. If ‘ROW’ ==  'TOTALROWS', then it implies that we are at the end of the column. So, return ('BAL' % 10 == 0 and isAnyMapping('WORDS', 0, ‘COL’ + 1, ‘BAL’ / 10, 'LETTODIG', ‘DIGTOLET’,  'TOTALROWS', 'TOTALCOLS' ).
3. Create a new string ‘W’ to store the current word, ‘W’ = ‘WORDS[ROW]'.
4. If ‘COL’ >= length of the ‘W’ (this can happen if the current word has a smaller length), then return the function isAnyMapping('WORDS', ‘ROW’ + 1, ‘COL’, ‘BAL’, 'LETTODIG', ‘DIGTOLET’,  'TOTALROWS', 'TOTALCOLS' ).
5. Create a variable ‘LETTER’ of data type char and set it with the current character of the word.
6. Create a new variable ‘SIGN’. Make it as 1 if we are not in the last row. Else, it is -1. This variable is used to find whether we have to add the digit or subtract the digit.
7. If we have a prior mapping and if this mapping is valid, i.e., it will not have leading zeros, then call the function again by using the prior mapping. To check whether the prior mapping is valid or not, we can use the following conditions:
   • If ‘LETTER’ is present in the HashMap 'LETTODIG' and ('LETTODIG[LETTER]' != 0 or (if ‘LETTODIG[LETTER]’ == 0 and W.length() == 1) or ‘COL’ != W.length() - 1), then:
     • return isAnyMapping('WORDS', ‘ROW’ + 1, ‘COL’, ‘BAL’ + ‘SIGN’ * ‘LETTODIG[LETTER]’, 'LETTODIG', ‘DIGTOLET’, 'TOTALROWS', 'TOTALCOLS' ).
8. Else, we have to find a new mapping. So, run a loop with variable i from 0 to 10, in each iteration:
   • if('DIGTOLET[i]' == ‘-’ and ('i' != 0 or ('i' == 0 and W.length() == 1) or ‘COL’ != W.length() - 1), then:
     • ‘DIGTOLET[i]’ = ‘LETTER’
     • ‘LETTODIG[LETTER]’ = ‘i’
     • ‘X’ = isAnyMapping( 'WORDS', ‘ROW’ + 1, ‘COL’, ‘BAL’ + ‘SIGN’ * ‘LETTODIG[LETTER]’, 'LETTODIG', ‘DIGTOLET’, 'TOTALROWS', 'TOTALCOLS' ).
     • If ‘X’ is true, then return true.
     • ‘DIGTOLET[i]’ = ‘-’
     • If the letter to digit mapping present in the HashMap 'LETTODIG', then remove this mapping.
9. Finally, return false.

O(N!), where N is the number of different characters used in the expression.

In the worst case, we have to check all possible combinations of the letter to the digit mapping, and at most, we can have N different letters. So, the time complexity will be O(N!).

O(N), where N is the number of different characters used in the expression.

As we are creating a HashMap for the letter to the digit mapping, which can store at most N characters in the worst condition and also recursion stack used for calling the function would be used for all the N characters. Hence, the overall space complexity will be O(N).