Leetcode 1307. Verbal Arithmetic Puzzle
Problem Explanation:
This is a problem about mapping numbers to words, similar to the classic problem of cryptarithms where mathematical expressions involve letters instead of actual numbers. The idea is to assign each letter in the words and the result a unique digit, form numbers by these assignments, and check if the equality is maintained. In all these assignments, no leading zeroes are allowed, i.e., no word can start with a zero.
For example, with words = ["SEND", "MORE"]
and result = "MONEY"
, we can assign 'S'-> 9, 'E'->5, 'N'->6, 'D'->7, 'M'->1, 'O'->0, 'R'->8, 'Y'->'2'. This forms: `"SEND"(9567) + "MORE"(1085) = "MONEY"(10652), which is a valid equation.
Solution Approach:
The solution uses depth-first search (DFS) to fill the paths from all digits (0-9), tracking the ones already used. At each step, we check the current position in all words and the resulting word. We start from the least significant positions, i.e., from the rightmost characters, and go to the leftmost characters.
For each remaining character in this column for each word, we either fill in a digit that has not been used before, or if this character has been assigned a digit before, we just continue to the next character.
If we have looked at all the characters in this column for all the words, we then check if the sum of the assigned digits for this column matches the digit in the corresponding result column. If yes, we continue to the next column; if not, we stop and backtrack.
Let's walk through this in the example words = ["SEND", "MORE"]
and result = "MONEY"
:
- Start with the rightmost column, 'D' in 'SEND' and 'E' in 'MORE'. Let's assign 'D' -> 7 and 'E' -> 5.
- Next, the 'N' in 'SEND' and 'R' in 'MORE'. We assign 'N' -> 6 and 'R' -> 8.
- For the third column, 'E' in 'SEND' has been assigned, then we assign 'O' in 'MORE' -> 0, 'S' in 'SEND' -> 9, 'M' in 'MORE' -> 1.
- The last column 'M' in 'MONEY' -> 1.
- Since 'S', 'E', 'N', 'D', 'M', 'O', 'R', 'Y' in 'MONEY' have all been assigned and the formed numbers give a valid equation, we stop and return True.
C++ Solution:
1
2cpp
3class Solution {
4 public:
5 bool isSolvable(vector<string>& words, string result) {
6 vector<bool> usedDigit(10);
7 words.push_back(result);
8 int rows = words.size();
9 int cols = 0;
10 for (const string& word : words) cols = max(cols, int(word.length()));
11 return dfs(words, 0, 0, 0, cols, usedDigit);
12 }
13
14 bool dfs(vector<string>& words, int row, int col, int sum, const int cols, vector<bool>& usedDigit) {
15 unordered_map<char, int> letterToDigit;
16
17 if (col == cols) return sum == 0;
18 if (row == rows) return sum % 10 == 0 && dfs(words, 0, col + 1, sum / 10, cols, usedDigit);
19
20 string word = words[row];
21 if (col >= word.length()) return dfs(words, row + 1, col, sum, cols, usedDigit);
22
23 char letter = word[word.length() - col - 1];
24 int sign = row == rows - 1 ? -1 : 1;
25
26 if (const auto it = letterToDigit.find(letter); it != letterToDigit.end() && (it->second > 0 || col < word.length() - 1))
27 return dfs(words, row + 1, col, sum + sign * letterToDigit[letter], cols, usedDigit);
28
29 for (int digit = 0; digit < 10; ++digit)
30 if (!usedDigit[digit] && (digit > 0 || col + 1 < word.length())) {
31 letterToDigit[letter] = digit;
32 usedDigit[digit] = true;
33 if (dfs(words, row + 1, col, sum + sign * digit, cols, usedDigit)) return true;
34 usedDigit[digit] = false;
35 letterToDigit.erase(letter);
36 }
37
38 return false;
39 }
40};
Note:
Due to the time constraint, solutions in other languages could not be provided.# Python Solution:
1 2python 3class Solution: 4 def isSolvable(self, words, result): 5 n = max(map(len, words + [result])) 6 words = [word.rjust(n, '#') for word in words] 7 result = result.rjust(n, '#') 8 9 used = [0]*10 10 dict_ = {} 11 self.words = words 12 self.result = result 13 return self.dfs(n-1, 0, used, dict_) 14 15 def dfs(self, i, carry, used, dict_): 16 m, n = len(self.words), len(self.result) 17 if i < 0: 18 return carry == 0 19 20 s = carry 21 for j in range(m): 22 if self.words[j][i] == '#': continue 23 if self.words[j][i] not in dict_: 24 for k in range(10): 25 if used[k]: continue 26 if self.words[j][i-1] != '#' and k == 0: continue 27 dict_[self.words[j][i]] = k 28 used[k] = 1 29 s += dict_[self.words[j][i]] 30 if self.dfs(i-1, s//10, used, dict_): return True 31 s -= dict_[self.words[j][i]] 32 used[k] = 0 33 del dict_[self.words[j][i]] 34 return False 35 36 s += dict_[self.words[j][i]] 37 38 if self.result[i] not in dict_: 39 if used[s%10] or (self.result[i-1] != '#' and s%10 == 0): return False 40 dict_[self.result[i]] = s%10 41 used[s%10] = 1 42 if self.dfs(i-1, s//10, used, dict_): return True 43 used[s%10] = 0 44 del dict_[self.result[i]] 45 return False 46 47 return s%10 == dict_[self.result[i]] and self.dfs(i-1, s//10, used, dict_) 48 49 50# Test the solution 51words = ["SEND", "MORE"] 52result = "MONEY" 53sol = Solution() 54print(sol.isSolvable(words, result)) # Should print True
JavaScript Solution
1
2javascript
3var isSolvable=function(words, result) {
4 const map = new Map()
5 const used = new Set()
6 const isFirst = new Set()
7 for (let word of words.concat([result])) for (let i = 0; i < word.length; ++i) {
8 if (i === 0 && word.length > 1) isFirst.add(word[i])
9 if (!map.has(word[i])) map.set(word[i], [])
10 map.get(word[i]).push([words.indexOf(word), word.length - 1 - i])
11 }
12 words = words.map(word => [...word].reverse().join(''))
13
14 result = [...result].reverse().join('')
15 const dfs = (str, i, sum) => {
16 if (i === 10) return sum === 0
17 if (sum % (1 << 10) != (str[i] || 0) - '0'.charCodeAt()) return false
18 if (i === str.length) return sum === 0
19 for (let j = (isFirst.has(result[i]) ? 1 : 0); j < 10; ++j) {
20 if (used.has(j)) continue
21 const next = []
22 let carry = sum >> 10
23 for (let [idx, exp] of map.get(result[i]) || []) {
24 if (words[idx][exp] === undefined) next.push(j << exp)
25 else {
26 if ((carry & 1) != (words[idx][exp].charCodeAt() + j >> exp & 1)) return false
27 words[idx] = words[idx].substring(0, exp) + String.fromCharCode((words[idx][exp].charCodeAt() + j >> exp) % 10 + '0'.charCodeAt()) + words[idx].substring(exp + 1)
28 }
29 carry >>= 1
30 }
31 next.push(j << i)
32 used.add(j)
33 if (dfs(str, i + 1, sum + (carry << 10) + next.reduce((a, b) => a + b, 0))) return true
34 used.delete(j)
35 for (let k = next.length - 1; k >= 0; --k) {
36 let [idx, exp] = map.get(result[i])[k] || []
37 if (words[idx] === undefined) continue
38 words[idx] = words[idx].substring(0, exp) + String.fromCharCode((words[idx].substring(exp, exp + 1).charCodeAt() + 10 - j % 10) % 10 + '0'.charCodeAt()) + words[idx].substring(exp + 1)
39 }
40 }
41 return false
42 }
43 return dfs(result, 0, 0)
44};
45
46words = ["ACCA", "DDA"];
47result = "ADDC";
48console.log(words, result, isSolvable(words, result));
Got a question?ย Ask the Teaching Assistantย anything you don't understand.
Still not clear? Ask in the Forum, ย Discordย orย Submitย the part you don't understand to our editors.