Verbal Arithmetic Puzzle
Verbal Arithmetic Puzzle is a hard recursion & backtracking problem solved with the permutations pattern.
The best approach, optimal (column-by-column backtracking with carry), runs in O(10! / (10 − L)!) worst case time and O(L + n · m) space.
Below are 2 approaches in Java, Python, C++ and JavaScript, from letter weights + full assignment up.
Problem
You are given an addition puzzle written with letters: the words in words are added together, and their sum should be result. Decide whether the letters can be replaced by digits so that the addition is correct.
The rules: every letter stands for exactly one digit 0–9, different letters stand for different digits, and a number made of two or more letters may not start with 0 (a one-letter number may be 0). Return true if such an assignment exists, otherwise false.
Examples
Example 1
- Input
words = ["TO", "GO"], result = "OUT"- Output
true- Why
- T = 2, O = 1, G = 8, U = 0 gives 21 + 81 = 102.
Example 2
- Input
words = ["AB", "AB"], result = "AB"- Output
false- Why
- x + x = x forces x = 0, but AB has two letters, so A cannot be 0.
Example 3
- Input
words = ["X", "Y", "Z"], result = "XY"- Output
true- Why
- X = 1, Y = 0, Z = 9 gives 1 + 0 + 9 = 10. A one-letter number may be 0.
Constraints
2 <= words.length <= 51 <= words[i].length, result.length <= 7words[i]andresultcontain only uppercase English letters.- At most
10different letters appear in the whole puzzle.
Solve it here
Write your solution in Java, Python, C++ or JavaScript and run it against the examples, right in the page. Submit runs the hidden tests too and, with a free account, records the solve in your revision log.
Your own testcases: Run checks these, and the expected output comes from our reference solution.
My submissions
Nothing yet. Every Run and Submit you make while signed in shows up here.
| When | Result | Tests | Runtime | Your time | Type |
|---|
Run checks the testcases above (3 examples, or your own). Submit also runs 18 hidden tests and saves the solve to your log. Signed in, every Run and Submit is saved under My submissions; your draft stays in this browser.
Solutions
Try it yourself first. Then compare: each approach lists its idea, the steps, its time and space, and the code in Java, Python, C++ and JavaScript.
| Approach | Time | Space |
|---|---|---|
| Letter weights + full assignment | O(10! / (10 − L)!) | O(L) |
| Optimal (column-by-column backtracking with carry) | O(10! / (10 − L)!) worst case | O(L + n · m) |
1Letter weights + full assignment
O(10! / (10 − L)!)L ≤ 10 distinct letters; all ordered assignments of L digits may be tried, about 3.6 million when L = 10.O(L)Recursion depth L plus fixed-size arrays.Turn the equation into one linear sum: a letter at position p (from the right) adds 10^p to its weight when it is in a word and subtracts 10^p when it is in the result. Try every injective assignment of digits to the distinct letters (respecting the no-leading-zero rule) and accept when the weighted sum is 0.
- Compute
weight[c]for each letter and mark letters that start a multi-letter word or result. - Backtrack over the distinct letters, giving each an unused digit (not 0 for leading letters) and adding
weight × digitto a running sum. - When every letter has a digit, succeed if the sum is 0.
class Solution {
public boolean isSolvable(String[] words, String result) {
int[] weight = new int[26];
boolean[] lead = new boolean[26];
boolean[] present = new boolean[26];
for (String w : words) addWord(w, 1, weight, lead, present);
addWord(result, -1, weight, lead, present);
List<Integer> letters = new ArrayList<>();
for (int c = 0; c < 26; c++) if (present[c]) letters.add(c);
return assign(0, letters, weight, lead, new boolean[10], 0L);
}
private void addWord(String w, int sign, int[] weight, boolean[] lead, boolean[] present) {
int place = 1;
for (int i = w.length() - 1; i >= 0; i--) {
int c = w.charAt(i) - 'A';
weight[c] += sign * place;
present[c] = true;
place *= 10;
}
if (w.length() > 1) lead[w.charAt(0) - 'A'] = true;
}
private boolean assign(int i, List<Integer> letters, int[] weight, boolean[] lead, boolean[] used, long sum) {
if (i == letters.size()) return sum == 0;
int c = letters.get(i);
for (int d = 0; d <= 9; d++) {
if (used[d] || (d == 0 && lead[c])) continue;
used[d] = true;
if (assign(i + 1, letters, weight, lead, used, sum + (long) weight[c] * d)) return true;
used[d] = false;
}
return false;
}
}class Solution:
def isSolvable(self, words: List[str], result: str) -> bool:
weight = [0] * 26
lead = [False] * 26
present = [False] * 26
for w in words:
self.addWord(w, 1, weight, lead, present)
self.addWord(result, -1, weight, lead, present)
letters = [c for c in range(26) if present[c]]
return self.assign(0, letters, weight, lead, [False] * 10, 0)
def addWord(self, w: str, sign: int, weight: List[int], lead: List[bool], present: List[bool]) -> None:
place = 1
for ch in reversed(w):
c = ord(ch) - 65
weight[c] += sign * place
present[c] = True
place *= 10
if len(w) > 1:
lead[ord(w[0]) - 65] = True
def assign(self, i: int, letters: List[int], weight: List[int], lead: List[bool], used: List[bool], total: int) -> bool:
if i == len(letters):
return total == 0
c = letters[i]
for d in range(10):
if used[d] or (d == 0 and lead[c]):
continue
used[d] = True
if self.assign(i + 1, letters, weight, lead, used, total + weight[c] * d):
return True
used[d] = False
return Falseclass Solution {
public:
bool isSolvable(vector<string>& words, string result) {
vector<int> weight(26, 0);
vector<bool> lead(26, false), present(26, false);
for (auto& w : words) addWord(w, 1, weight, lead, present);
addWord(result, -1, weight, lead, present);
vector<int> letters;
for (int c = 0; c < 26; c++) if (present[c]) letters.push_back(c);
vector<bool> used(10, false);
return assign(0, letters, weight, lead, used, 0LL);
}
private:
void addWord(const string& w, int sign, vector<int>& weight, vector<bool>& lead, vector<bool>& present) {
int place = 1;
for (int i = (int) w.size() - 1; i >= 0; i--) {
int c = w[i] - 'A';
weight[c] += sign * place;
present[c] = true;
place *= 10;
}
if (w.size() > 1) lead[w[0] - 'A'] = true;
}
bool assign(size_t i, const vector<int>& letters, const vector<int>& weight, const vector<bool>& lead, vector<bool>& used, long long sum) {
if (i == letters.size()) return sum == 0;
int c = letters[i];
for (int d = 0; d <= 9; d++) {
if (used[d] || (d == 0 && lead[c])) continue;
used[d] = true;
if (assign(i + 1, letters, weight, lead, used, sum + (long long) weight[c] * d)) return true;
used[d] = false;
}
return false;
}
};function isSolvable(words, result) {
const weight = new Array(26).fill(0);
const lead = new Array(26).fill(false);
const present = new Array(26).fill(false);
for (const w of words) addWord(w, 1, weight, lead, present);
addWord(result, -1, weight, lead, present);
const letters = [];
for (let c = 0; c < 26; c++) if (present[c]) letters.push(c);
return assign(0, letters, weight, lead, new Array(10).fill(false), 0);
}
function addWord(w, sign, weight, lead, present) {
let place = 1;
for (let i = w.length - 1; i >= 0; i--) {
const c = w.charCodeAt(i) - 65;
weight[c] += sign * place;
present[c] = true;
place *= 10;
}
if (w.length > 1) lead[w.charCodeAt(0) - 65] = true;
}
function assign(i, letters, weight, lead, used, sum) {
if (i === letters.length) return sum === 0;
const c = letters[i];
for (let d = 0; d <= 9; d++) {
if (used[d] || (d === 0 && lead[c])) continue;
used[d] = true;
if (assign(i + 1, letters, weight, lead, used, sum + weight[c] * d)) return true;
used[d] = false;
}
return false;
}2Optimal (column-by-column backtracking with carry)
O(10! / (10 − L)!) worst caseThe bound is the same, but every result letter is forced rather than tried, and a wrong column fails right away, so far fewer branches are explored in practice.O(L + n · m)Recursion depth is at most the number of (column, word) cells, n · m ≤ 6 · 7, plus the 26-letter tables.Add the numbers the way you would by hand, from the rightmost column. Walk the words of the current column one by one, assigning a digit only when a letter is still free, and keep the running column sum. When the column is done, the result's letter in that column must equal sum % 10: it is either checked or forced, never guessed, and sum / 10 carries into the next column. Contradictions show up after a few letters instead of after all of them.
- If any word is longer than
result, return false. Mark leading letters of multi-letter words and of the result. - solve(col, row, carry): if
col == result.length, succeed iffcarry == 0. - While
row < words.length: skip words too short forcol; if the column letter has a digit, add it; otherwise try every allowed unused digit. - After the last word: the result letter must be
carry % 10(check it, or assign it if free and allowed), then continue withsolve(col + 1, 0, carry / 10). - Undo assignments when backtracking.
class Solution {
private String[] words;
private String result;
private int[] digitOf;
private boolean[] used;
private boolean[] lead;
public boolean isSolvable(String[] words, String result) {
this.words = words;
this.result = result;
for (String w : words) if (w.length() > result.length()) return false;
digitOf = new int[26];
Arrays.fill(digitOf, -1);
used = new boolean[10];
lead = new boolean[26];
for (String w : words) if (w.length() > 1) lead[w.charAt(0) - 'A'] = true;
if (result.length() > 1) lead[result.charAt(0) - 'A'] = true;
return solve(0, 0, 0);
}
private boolean solve(int col, int row, int carry) {
if (col == result.length()) return carry == 0;
if (row < words.length) {
String w = words[row];
if (col >= w.length()) return solve(col, row + 1, carry);
int c = w.charAt(w.length() - 1 - col) - 'A';
if (digitOf[c] >= 0) return solve(col, row + 1, carry + digitOf[c]);
for (int d = 0; d <= 9; d++) {
if (used[d] || (d == 0 && lead[c])) continue;
digitOf[c] = d;
used[d] = true;
if (solve(col, row + 1, carry + d)) return true;
digitOf[c] = -1;
used[d] = false;
}
return false;
}
int c = result.charAt(result.length() - 1 - col) - 'A';
int d = carry % 10;
if (digitOf[c] >= 0) return digitOf[c] == d && solve(col + 1, 0, carry / 10);
if (used[d] || (d == 0 && lead[c])) return false;
digitOf[c] = d;
used[d] = true;
if (solve(col + 1, 0, carry / 10)) return true;
digitOf[c] = -1;
used[d] = false;
return false;
}
}class Solution:
def isSolvable(self, words: List[str], result: str) -> bool:
self.words = words
self.result = result
if any(len(w) > len(result) for w in words):
return False
self.digit_of = [-1] * 26
self.used = [False] * 10
self.lead = [False] * 26
for w in words:
if len(w) > 1:
self.lead[ord(w[0]) - 65] = True
if len(result) > 1:
self.lead[ord(result[0]) - 65] = True
return self.solve(0, 0, 0)
def solve(self, col: int, row: int, carry: int) -> bool:
if col == len(self.result):
return carry == 0
if row < len(self.words):
w = self.words[row]
if col >= len(w):
return self.solve(col, row + 1, carry)
c = ord(w[len(w) - 1 - col]) - 65
if self.digit_of[c] >= 0:
return self.solve(col, row + 1, carry + self.digit_of[c])
for d in range(10):
if self.used[d] or (d == 0 and self.lead[c]):
continue
self.digit_of[c] = d
self.used[d] = True
if self.solve(col, row + 1, carry + d):
return True
self.digit_of[c] = -1
self.used[d] = False
return False
c = ord(self.result[len(self.result) - 1 - col]) - 65
d = carry % 10
if self.digit_of[c] >= 0:
return self.digit_of[c] == d and self.solve(col + 1, 0, carry // 10)
if self.used[d] or (d == 0 and self.lead[c]):
return False
self.digit_of[c] = d
self.used[d] = True
if self.solve(col + 1, 0, carry // 10):
return True
self.digit_of[c] = -1
self.used[d] = False
return Falseclass Solution {
public:
bool isSolvable(vector<string>& words, string result) {
this->words = words;
this->result = result;
for (auto& w : words) if (w.size() > result.size()) return false;
digitOf.assign(26, -1);
used.assign(10, false);
lead.assign(26, false);
for (auto& w : words) if (w.size() > 1) lead[w[0] - 'A'] = true;
if (result.size() > 1) lead[result[0] - 'A'] = true;
return solve(0, 0, 0);
}
private:
vector<string> words;
string result;
vector<int> digitOf;
vector<bool> used, lead;
bool solve(int col, int row, int carry) {
if (col == (int) result.size()) return carry == 0;
if (row < (int) words.size()) {
const string& w = words[row];
if (col >= (int) w.size()) return solve(col, row + 1, carry);
int c = w[w.size() - 1 - col] - 'A';
if (digitOf[c] >= 0) return solve(col, row + 1, carry + digitOf[c]);
for (int d = 0; d <= 9; d++) {
if (used[d] || (d == 0 && lead[c])) continue;
digitOf[c] = d;
used[d] = true;
if (solve(col, row + 1, carry + d)) return true;
digitOf[c] = -1;
used[d] = false;
}
return false;
}
int c = result[result.size() - 1 - col] - 'A';
int d = carry % 10;
if (digitOf[c] >= 0) return digitOf[c] == d && solve(col + 1, 0, carry / 10);
if (used[d] || (d == 0 && lead[c])) return false;
digitOf[c] = d;
used[d] = true;
if (solve(col + 1, 0, carry / 10)) return true;
digitOf[c] = -1;
used[d] = false;
return false;
}
};function isSolvable(words, result) {
for (const w of words) if (w.length > result.length) return false;
const digitOf = new Array(26).fill(-1);
const used = new Array(10).fill(false);
const lead = new Array(26).fill(false);
for (const w of words) if (w.length > 1) lead[w.charCodeAt(0) - 65] = true;
if (result.length > 1) lead[result.charCodeAt(0) - 65] = true;
function solve(col, row, carry) {
if (col === result.length) return carry === 0;
if (row < words.length) {
const w = words[row];
if (col >= w.length) return solve(col, row + 1, carry);
const c = w.charCodeAt(w.length - 1 - col) - 65;
if (digitOf[c] >= 0) return solve(col, row + 1, carry + digitOf[c]);
for (let d = 0; d <= 9; d++) {
if (used[d] || (d === 0 && lead[c])) continue;
digitOf[c] = d;
used[d] = true;
if (solve(col, row + 1, carry + d)) return true;
digitOf[c] = -1;
used[d] = false;
}
return false;
}
const c = result.charCodeAt(result.length - 1 - col) - 65;
const d = carry % 10;
if (digitOf[c] >= 0) return digitOf[c] === d && solve(col + 1, 0, Math.floor(carry / 10));
if (used[d] || (d === 0 && lead[c])) return false;
digitOf[c] = d;
used[d] = true;
if (solve(col + 1, 0, Math.floor(carry / 10))) return true;
digitOf[c] = -1;
used[d] = false;
return false;
}
return solve(0, 0, 0);
}Edge cases to test
- A word longer than the result (never solvable)
- Single-letter words, which are allowed to be 0
- The same word repeated several times
- A result that is longer than any word by two or more letters
- All 10 digits in use
Hints
Hint 1
Each letter gets a different digit, and only numbers with more than one digit are forbidden from starting with 0. Backtracking over letter → digit assignments covers every case.
Hint 2
Give every letter a weight: its place value summed over the words, minus its place value in the result. The puzzle is solved when Σ weight × digit = 0.
Hint 3
To prune early, fill the columns from the rightmost one, like adding by hand: once a column's letters are known, the result letter is forced to (column sum + carry) % 10.
FAQ
What is the best time complexity for Verbal Arithmetic Puzzle?
Optimal (column-by-column backtracking with carry) runs in O(10! / (10 − L)!) worst case time and O(L + n · m) extra space. The bound is the same, but every result letter is forced rather than tried, and a wrong column fails right away, so far fewer branches are explored in practice.
Which pattern does Verbal Arithmetic Puzzle use?
It is a recursion & backtracking problem that uses the permutations pattern. Other problems with the same pattern: Permutations - Swap Trick, Permutations, Permutations II.
Is there a brute force solution for Verbal Arithmetic Puzzle?
Yes. Letter weights + full assignment takes O(10! / (10 − L)!) time and O(L) space. Turn the equation into one linear sum: a letter at position p (from the right) adds 10^p to its weight when it is in a word and subtracts 10^p when it is in the result.
Which edge cases should I test for Verbal Arithmetic Puzzle?
A word longer than the result (never solvable); Single-letter words, which are allowed to be 0; The same word repeated several times; A result that is longer than any word by two or more letters; All 10 digits in use.