Leetcode: Verbal Arithmetic Puzzle
This question is asked at Atlassian. Given an equation represented by words on the left side and the result on the right side, we need to check if the equation is solvable under the following rules such that each character is decoded as one digit, every pair of different characters map to different digits, and each words[i] and result are decoded as one number without the leading zeros and the sum of the numbers of the left side will equal to the sum of the numbers on the right side. We want to see if the equation is solvable in that way.
Here is the example:
Input: words = ["SEND","MORE"], result = "MONEY"
Output: true
Explanation: Map 'S'-> 9, 'E'->5, 'N'->6, 'D'->7, 'M'->1, 'O'->0, 'R'->8, 'Y'->'2'
Such that: "SEND" + "MORE" = "MONEY" , 9567 + 1085 = 10652
2 letters to the same number means that there can only be up to 10 unique letters at a time.
We can't think of some type of heuristic to come up with a mapping so we'll need to think about exhaustive search or backtracking.
You start from the left hand side and infer your way through.
class Solution {
private static final int[] POW_10 = new int[]{1, 10, 100, 1000, 10000, 100000, 1000000};
public boolean isSolvable(String[] words, String result) {
Set<Character> charSet = new HashSet<>(); //Hashset to store all potential characters.
int[] charCount = new int[91];
boolean[] nonLeadingZero = new boolean[91]; // ASCII of `A..Z` chars are in range `65..90`
for (String word : words) {
char[] cs = word.toCharArray();
for (int i = 0; i < cs.length; i++) {
if (i == 0 && cs.length > 1) nonLeadingZero[cs[i]] = true; //set nonleading 0 to the first
charSet.add(cs[i]); //add character to the char set
charCount[cs[i]] += POW_10[cs.length - i - 1]; // charCount is calculated by units and place and assign a particular number to this slot.
}
}
char[] cs = result.toCharArray();
for (int i = 0; i < cs.length; i++) {
if (i == 0 && cs.length > 1) nonLeadingZero[cs[i]] = true;
charSet.add(cs[i]);
charCount[cs[i]] -= POW_10[cs.length - i - 1]; // charCount is calculated by units
}
boolean[] used = new boolean[10]; //we only have 10 characters. Check if they are used or not.
char[] charList = new char[charSet.size()];
int i = 0;
for (char c : charSet) charList[i++] = c;
return backtracking(used, charList, nonLeadingZero, 0, 0, charCount); //backtrack the character and see if we can get the optimal result.
}
private boolean backtracking(boolean[] used, char[] charList, boolean[] nonLeadingZero, int step, int diff, int[] charCount) {
if (step == charList.length) return diff == 0; // difference between sum of words and result equal to 0
for (int d = 0; d <= 9; d++) { // each character is decoded as one digit (0 - 9).
char c = charList[step];
if (!used[d] // each different characters must map to different digits
&& (d > 0 || !nonLeadingZero[c])) { // decoded as one number without leading zeros, if there is no leading 0 then this number is used.
used[d] = true;
if (backtracking(used, charList, nonLeadingZero, step + 1, diff + charCount[c] * d, charCount)) return true; //try to backtrack based on this nonleading 0
used[d] = false;
}
}
return false;
}
}
However, there's a rule, where you can't have leading zero's. We first add the words that represent the equation and subtract the potential solution. We want the balance to be 0 in each column. We need to know when to have solution. We also need to know when to exit. When we are in the last column, we're done. When we are in the last column, we return columns are equal to 0. We want to balance to be equal to 0 for each column.
class Solution(object):
def isSolvable(self, words, result):
words.append(result) #append the result to the words
rows, cols = len(words), max(map(len, words)) # number of rows is the number of words, and the number of columns is the lengh of the longest word.
letterToDigit = {} #Mapping letter to the digit.
digitToLetter = [None] * 10 #Maps each digit to a specific letter which the letter is assigned the the specific digit index.
def search(col, row, bal):
if column >= cols: #if we are at the leftmost character, we're done and we check whether the sum equals to 0.
return bal == 0
if rows == rows: #we see if we have last row
return bal % 10 == 0 and search(column + 1, 0, bal // 10) #next column, first row (ones place) start the calculation all over again by taking the balance We first see if the ones place equals to zero and go to the left and compute that.
word = words[row] #Go to the last word.
if column >= len(word):
return search(column, row + 1, bal)
letter = word[~column] #the letter that you access is the word index at the length of the array - the column, which is the columnth last index.
sign = 1 if row < (rows - 1) else -1 #sign is -1 for the result row else it's 1. This is because you add all the numbers and you subtract the last number.
#if the digital assignment already exists, use it
for d,c in enumarate(digitToLetter):
if c is None and (d or column != len(word) - 1): #Avoid leading zeros
#choose
digitToLetter[d] = letter #assign the letter to the particular digit
letterToDigit[letter] = d #map the digit to the particular letter
#add or subtract the particular digit and go to the next row to iterate.
if search(column, row + 1, bal + sign * d):
return True
#unchoose if this doesn't work.
digitToLetter[d] = None
if letter in letterToDigit:
#delete the letter mapping. go over the for loop again and try another iteration.
del letterToDigit[letter]
#cannot find a solution.
return False
#search from beginning.
return search(0,0,0)
Comments
Post a Comment