Verbal Arithmetic Puzzle — Hard Problem & Solution

Problem statement

A cryptarithm: every uppercase letter stands for a decimal digit. Decide whether the letters can be assigned digits so that the sum of the numbers spelled by words equals the number spelled by result.

The assignment must follow these rules:

• Each letter gets one digit, and different letters get different digits.
• No number may have a leading zero: the first letter of any word (or of result) that is longer than one letter cannot be 0. A one-letter word may be 0.

Return true if such an assignment exists.

Example 1

Input: words = ["TO","GO"], result = "OUT"
Output: true
Explanation: T = 2, O = 1, G = 8, U = 0: 21 + 81 = 102.

Example 2

Input: words = ["A","B"], result = "CDE"
Output: false
Explanation: Two digits add up to at most 18, never a three-digit number.

Example 3

Input: words = ["SEND","MORE"], result = "MONEY"
Output: true
Explanation: 9567 + 1085 = 10652.

Constraints

• 2 <= words.length <= 5
• 1 <= words[i].length, result.length <= 7
• words[i] and result consist of uppercase English letters
• At most 10 different letters appear in the whole puzzle

How to solve Verbal Arithmetic Puzzle

Simulate column addition from right to left while assigning digits lazily. Each result letter's digit is forced by the column sum, so most wrong partial assignments are rejected after a single column.

Approach

1. If any word is longer than result, return false. Mark the first letter of every word or result with length > 1 as non-zero.
2. solve(col, row, sum): if col == len(result), succeed exactly when sum == 0 (no carry left).
3. While row points at a word: if the word has no digit in this column, move to the next row; if its letter is assigned, add its digit; otherwise try every free digit (not 0 for a leading letter), add it and recurse on the next row.
4. When row reaches the result: the needed digit is sum % 10. If the result letter is assigned it must match; otherwise the digit must be free (and non-zero if the letter is leading) — assign it. Continue with solve(col + 1, 0, sum / 10).
5. Undo every assignment when backtracking.

Why it works

Column addition is exactly how the sum is computed: the digit of result at a column is the column total modulo 10 and the rest is carried. By deciding letters in the order the paper algorithm reads them, every constraint is checked as soon as all of its letters are known, and the search still covers every injective assignment, so it answers correctly.

Complexity

• Time — O(10!) worst case; far smaller with column pruning
• Space — O(number of letters + columns)

Pitfalls

• A one-letter word or result may be 0; only multi-letter numbers forbid a leading zero.
• Without the final carry == 0 check, sums that overflow result look valid.
• A letter can appear in several words and in result; it must get the same digit everywhere.

Reference solution

Python

from typing import List

def isSolvable(words: List[str], result: str) -> bool:
    L = len(result)
    if any(len(w) > L for w in words):
        return False
    W = len(words)
    assign = [-1] * 26
    used = [False] * 10
    lead = [False] * 26
    for s in words + [result]:
        if len(s) > 1:
            lead[ord(s[0]) - 65] = True

    def solve(col, row, total):
        if col == L:
            return total == 0
        if row == W:
            rc = ord(result[L - 1 - col]) - 65
            d = total % 10
            if assign[rc] >= 0:
                return assign[rc] == d and solve(col + 1, 0, total // 10)
            if used[d] or (d == 0 and lead[rc]):
                return False
            assign[rc] = d
            used[d] = True
            ok = solve(col + 1, 0, total // 10)
            assign[rc] = -1
            used[d] = False
            return ok
        w = words[row]
        if col >= len(w):
            return solve(col, row + 1, total)
        c = ord(w[len(w) - 1 - col]) - 65
        if assign[c] >= 0:
            return solve(col, row + 1, total + assign[c])
        for d in range(10):
            if used[d] or (d == 0 and lead[c]):
                continue
            assign[c] = d
            used[d] = True
            ok = solve(col, row + 1, total + d)
            assign[c] = -1
            used[d] = False
            if ok:
                return True
        return False

    return solve(0, 0, 0)

JavaScript

var isSolvable = function(words, result) {
    var L = result.length;
    var W = words.length;
    for (var w = 0; w < W; w++) if (words[w].length > L) return false;
    var assign = new Array(26).fill(-1);
    var used = new Array(10).fill(false);
    var lead = new Array(26).fill(false);
    var rows = words.concat([result]);
    for (var r = 0; r < rows.length; r++) if (rows[r].length > 1) lead[rows[r].charCodeAt(0) - 65] = true;
    var solve = function(col, row, sum) {
        if (col === L) return sum === 0;
        if (row === W) {
            var rc = result.charCodeAt(L - 1 - col) - 65;
            var d = sum % 10;
            var carry = Math.floor(sum / 10);
            if (assign[rc] >= 0) return assign[rc] === d && solve(col + 1, 0, carry);
            if (used[d] || (d === 0 && lead[rc])) return false;
            assign[rc] = d;
            used[d] = true;
            var ok = solve(col + 1, 0, carry);
            assign[rc] = -1;
            used[d] = false;
            return ok;
        }
        var word = words[row];
        if (col >= word.length) return solve(col, row + 1, sum);
        var c = word.charCodeAt(word.length - 1 - col) - 65;
        if (assign[c] >= 0) return solve(col, row + 1, sum + assign[c]);
        for (var dd = 0; dd <= 9; dd++) {
            if (used[dd] || (dd === 0 && lead[c])) continue;
            assign[c] = dd;
            used[dd] = true;
            var good = solve(col, row + 1, sum + dd);
            assign[c] = -1;
            used[dd] = false;
            if (good) return true;
        }
        return false;
    };
    return solve(0, 0, 0);
};

Also on the editorial tab: C, C#, C++, Go, Java, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

More arrays problems

• Remove Boxes Hard
• Number of Squareful Arrays Hard
• Closest Subsequence Sum Hard
• Maximum Number of Achievable Transfer Requests Hard
• 24 Game Hard
• Distribute Repeating Integers Hard