Verbal Arithmetic Puzzle

Hard Recursion & Backtracking Permutations Original on LeetCode

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 <= 5
  • 1 <= words[i].length, result.length <= 7
  • words[i] and result contain only uppercase English letters.
  • At most 10 different 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.

00:00
Testcase

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.

ApproachTimeSpace
Letter weights + full assignmentO(10! / (10 − L)!)O(L)
Optimal (column-by-column backtracking with carry)O(10! / (10 − L)!) worst caseO(L + n · m)

1Letter weights + full assignment

TimeO(10! / (10 − L)!)L ≤ 10 distinct letters; all ordered assignments of L digits may be tried, about 3.6 million when L = 10.
SpaceO(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.

  1. Compute weight[c] for each letter and mark letters that start a multi-letter word or result.
  2. Backtrack over the distinct letters, giving each an unused digit (not 0 for leading letters) and adding weight × digit to a running sum.
  3. 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;
    }
}

2Optimal (column-by-column backtracking with carry)

TimeO(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.
SpaceO(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.

  1. If any word is longer than result, return false. Mark leading letters of multi-letter words and of the result.
  2. solve(col, row, carry): if col == result.length, succeed iff carry == 0.
  3. While row < words.length: skip words too short for col; if the column letter has a digit, add it; otherwise try every allowed unused digit.
  4. After the last word: the result letter must be carry % 10 (check it, or assign it if free and allowed), then continue with solve(col + 1, 0, carry / 10).
  5. 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;
    }
}

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.