Verbal Arithmetic Puzzle

Problem

Given an equation, represented by words on the left side and the result on the right side.

You need to check if the equation is solvable under the following rules:

• Each character is decoded as one digit (0 - 9).
• No two characters can map to the same digit.
• Each words[i] and result are decoded as one number without leading zeros.
• Sum of numbers on the left side (words) will equal to the number on the right side (result).

Return true if the equation is solvable, otherwise return false.

Examples

Example 1

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

Example 2

Input: words = ["SIX","SEVEN","SEVEN"], result = "TWENTY"
Output: true
Explanation: Map 'S'-> 6, 'I'->5, 'X'->0, 'E'->8, 'V'->7, 'N'->2, 'T'->1, 'W'->'3', 'Y'->4
Such that: "SIX" + "SEVEN" + "SEVEN" = "TWENTY" ,  650 + 68782 + 68782 = 138214

Example 3

Input: words = ["LEET","CODE"], result = "POINT"
Output: false
Explanation: There is no possible mapping to satisfy the equation, so we return false.
Note that two different characters cannot map to the same digit.

Constraints

• 2 <= words.length <= 5
• 1 <= words[i].length, result.length <= 7
• words[i], result contain only uppercase English letters.
• The number of different characters used in the expression is at most 10.

Solution

Method 1 – Coefficient Summation Backtracking (Baseline)

Intuition

Treat each letter as a variable with a linear coefficient equal to the (signed) sum of its positional weights across all addend words minus those in the result. If we assign digits to letters, the total weighted sum must be zero. This converts per-assignment validation into a single final sum check, allowing pruning only on simple constraints (used digits, leading zeros) but not early arithmetic inconsistencies column-by-column.

Approach

1. Collect unique letters; if > 10 → impossible.
2. Build coeff[c]: for each addend word add 10^k for position k from right; for result subtract 10^k.
3. Record leading (non-zero) letters of all multi-length words (including result) to enforce non-zero digit.
4. DFS over list of letters assigning unused digits (skipping 0 for leading letters).
5. At leaf, compute total = Σ coeff[c] * digit[c]; success if total == 0.

This does not prune partial sums; worst-case explores nearly all permutations.

Code

C++

#include <vector>
#include <string>
#include <unordered_map>
#include <unordered_set>
using namespace std;
class Solution {
public:
    bool isSolvable(vector<string>& words, string result) {
        unordered_set<char> chars_set;
        for (auto& w : words) for (char c : w) chars_set.insert(c);
        for (char c : result) chars_set.insert(c);
        if (chars_set.size() > 10) return false;
        vector<char> chars(chars_set.begin(), chars_set.end());
        unordered_set<char> first_letters;
        for (auto& w : words) first_letters.insert(w[0]);
        first_letters.insert(result[0]);
        unordered_map<char, int> coeff;
        for (auto& w : words) for (int i = 0; i < w.size(); ++i) coeff[w[w.size()-1-i]] += pow(10, i);
        for (int i = 0; i < result.size(); ++i) coeff[result[result.size()-1-i]] -= pow(10, i);
        vector<int> used(10, 0);
        unordered_map<char, int> char_to_digit;
        function<bool(int)> backtrack = [&](int idx) {
            if (idx == chars.size()) {
                long long total = 0;
                for (auto& [c, v] : coeff) total += v * char_to_digit[c];
                return total == 0;
            }
            char c = chars[idx];
            for (int d = 0; d < 10; ++d) {
                if (used[d]) continue;
                if (d == 0 && first_letters.count(c)) continue;
                char_to_digit[c] = d; used[d] = 1;
                if (backtrack(idx+1)) return true;
                used[d] = 0; char_to_digit.erase(c);
            }
            return false;
        };
        return backtrack(0);
    }
};

Go

func isSolvable(words []string, result string) bool {
    charsSet := map[byte]struct{}{}
    for _, w := range words {
        for i := 0; i < len(w); i++ {
            charsSet[w[i]] = struct{}{}
        }
    }
    for i := 0; i < len(result); i++ {
        charsSet[result[i]] = struct{}{}
    }
    if len(charsSet) > 10 {
        return false
    }
    chars := make([]byte, 0, 10)
    for c := range charsSet {
        chars = append(chars, c)
    }
    firstLetters := map[byte]struct{}{}
    for _, w := range words {
        firstLetters[w[0]] = struct{}{}
    }
    firstLetters[result[0]] = struct{}{}
    coeff := map[byte]int{}
    for _, w := range words {
        for i := 0; i < len(w); i++ {
            coeff[w[len(w)-1-i]] += pow10(i)
        }
    }
    for i := 0; i < len(result); i++ {
        coeff[result[len(result)-1-i]] -= pow10(i)
    }
    used := make([]bool, 10)
    charToDigit := map[byte]int{}
    var backtrack func(idx int) bool
    backtrack = func(idx int) bool {
        if idx == len(chars) {
            total := 0
            for c, v := range coeff {
                total += v * charToDigit[c]
            }
            return total == 0
        }
        c := chars[idx]
        for d := 0; d < 10; d++ {
            if used[d] { continue }
            if d == 0 {
                if _, ok := firstLetters[c]; ok { continue }
            }
            charToDigit[c] = d; used[d] = true
            if backtrack(idx+1) { return true }
            used[d] = false; delete(charToDigit, c)
        }
        return false
    }
    return backtrack(0)
}
func pow10(n int) int { res := 1; for i := 0; i < n; i++ { res *= 10 }; return res }

Java

import java.util.*;
class Solution {
    public boolean isSolvable(String[] words, String result) {
        Set<Character> charsSet = new HashSet<>();
        for (String w : words) for (char c : w.toCharArray()) charsSet.add(c);
        for (char c : result.toCharArray()) charsSet.add(c);
        if (charsSet.size() > 10) return false;
        List<Character> chars = new ArrayList<>(charsSet);
        Set<Character> firstLetters = new HashSet<>();
        for (String w : words) firstLetters.add(w.charAt(0));
        firstLetters.add(result.charAt(0));
        Map<Character, Integer> coeff = new HashMap<>();
        for (String w : words) for (int i = 0; i < w.length(); i++) coeff.put(w.charAt(w.length()-1-i), coeff.getOrDefault(w.charAt(w.length()-1-i), 0) + (int)Math.pow(10, i));
        for (int i = 0; i < result.length(); i++) coeff.put(result.charAt(result.length()-1-i), coeff.getOrDefault(result.charAt(result.length()-1-i), 0) - (int)Math.pow(10, i));
        boolean[] used = new boolean[10];
        Map<Character, Integer> charToDigit = new HashMap<>();
        return backtrack(0, chars, used, charToDigit, coeff, firstLetters);
    }
    private boolean backtrack(int idx, List<Character> chars, boolean[] used, Map<Character, Integer> charToDigit, Map<Character, Integer> coeff, Set<Character> firstLetters) {
        if (idx == chars.size()) {
            long total = 0;
            for (char c : coeff.keySet()) total += coeff.get(c) * charToDigit.get(c);
            return total == 0;
        }
        char c = chars.get(idx);
        for (int d = 0; d < 10; d++) {
            if (used[d]) continue;
            if (d == 0 && firstLetters.contains(c)) continue;
            charToDigit.put(c, d); used[d] = true;
            if (backtrack(idx+1, chars, used, charToDigit, coeff, firstLetters)) return true;
            used[d] = false; charToDigit.remove(c);
        }
        return false;
    }
}

Kotlin

class Solution {
    fun isSolvable(words: Array<String>, result: String): Boolean {
        val charsSet = mutableSetOf<Char>()
        words.forEach { w -> w.forEach { charsSet.add(it) } }
        result.forEach { charsSet.add(it) }
        if (charsSet.size > 10) return false
        val chars = charsSet.toList()
        val firstLetters = (words.map { it[0] } + result[0]).toSet()
        val coeff = mutableMapOf<Char, Int>()
        words.forEach { w -> w.reversed().forEachIndexed { i, c -> coeff[c] = coeff.getOrDefault(c, 0) + Math.pow(10.0, i.toDouble()).toInt() } }
        result.reversed().forEachIndexed { i, c -> coeff[c] = coeff.getOrDefault(c, 0) - Math.pow(10.0, i.toDouble()).toInt() }
        val used = BooleanArray(10)
        val charToDigit = mutableMapOf<Char, Int>()
        fun backtrack(idx: Int): Boolean {
            if (idx == chars.size) {
                var total = 0L
                for ((c, v) in coeff) total += v * charToDigit[c]!!
                return total == 0L
            }
            val c = chars[idx]
            for (d in 0..9) {
                if (used[d]) continue
                if (d == 0 && c in firstLetters) continue
                charToDigit[c] = d; used[d] = true
                if (backtrack(idx + 1)) return true
                used[d] = false; charToDigit.remove(c)
            }
            return false
        }
        return backtrack(0)
    }
}

Python

from typing import List
def isSolvable(words: List[str], result: str) -> bool:
    from collections import defaultdict
    # Step 1: Collect all unique characters
    chars = set(''.join(words) + result)
    if len(chars) > 10:
        return False
    chars = list(chars)
    # Step 2: Prepare for backtracking
    first_letters = set(w[0] for w in words + [result])
    n = len(chars)
    char_to_digit = {}
    used = [False] * 10
    # Precompute the coefficients for each character
    coeff = defaultdict(int)
    for w in words:
        for i, c in enumerate(w[::-1]):
            coeff[c] += 10 ** i
    for i, c in enumerate(result[::-1]):
        coeff[c] -= 10 ** i
    def backtrack(idx=0):
        if idx == n:
            # Check if the current assignment is valid
            total = 0
            for c in coeff:
                total += coeff[c] * char_to_digit[c]
            return total == 0
        c = chars[idx]
        for d in range(10):
            if used[d]:
                continue
            if d == 0 and c in first_letters:
                continue
            char_to_digit[c] = d
            used[d] = True
            if backtrack(idx + 1):
                return True
            used[d] = False
            del char_to_digit[c]
        return False
    return backtrack()

Rust

use std::collections::{HashMap, HashSet};
fn pow10(n: usize) -> i64 { (0..n).fold(1, |acc, _| acc * 10) }
pub fn is_solvable(words: Vec<&str>, result: &str) -> bool {
    let mut chars_set = HashSet::new();
    for w in &words { for c in w.chars() { chars_set.insert(c); } }
    for c in result.chars() { chars_set.insert(c); }
    if chars_set.len() > 10 { return false; }
    let chars: Vec<_> = chars_set.iter().cloned().collect();
    let mut first_letters = HashSet::new();
    for w in &words { first_letters.insert(w.chars().next().unwrap()); }
    first_letters.insert(result.chars().next().unwrap());
    let mut coeff = HashMap::new();
    for w in &words {
        for (i, c) in w.chars().rev().enumerate() {
            *coeff.entry(c).or_insert(0) += pow10(i) as i32;
        }
    }
    for (i, c) in result.chars().rev().enumerate() {
        *coeff.entry(c).or_insert(0) -= pow10(i) as i32;
    }
    let mut used = [false; 10];
    let mut char_to_digit = HashMap::new();
    fn backtrack(idx: usize, chars: &[char], used: &mut [bool; 10], char_to_digit: &mut HashMap<char, i32>, coeff: &HashMap<char, i32>, first_letters: &HashSet<char>) -> bool {
        if idx == chars.len() {
            let mut total = 0i64;
            for (&c, &v) in coeff.iter() {
                total += v as i64 * *char_to_digit.get(&c).unwrap() as i64;
            }
            return total == 0;
        }
        let c = chars[idx];
        for d in 0..10 {
            if used[d] { continue; }
            if d == 0 && first_letters.contains(&c) { continue; }
            char_to_digit.insert(c, d as i32); used[d] = true;
            if backtrack(idx+1, chars, used, char_to_digit, coeff, first_letters) { return true; }
            used[d] = false; char_to_digit.remove(&c);
        }
        false
    }
    backtrack(0, &chars, &mut used, &mut char_to_digit, &coeff, &first_letters)
}

TypeScript

function isSolvable(words: string[], result: string): boolean {
    const charsSet = new Set<string>();
    for (const w of words) for (const c of w) charsSet.add(c);
    for (const c of result) charsSet.add(c);
    if (charsSet.size > 10) return false;
    const chars = Array.from(charsSet);
    const firstLetters = new Set<string>([...words.map(w => w[0]), result[0]]);
    const coeff: Record<string, number> = {};
    for (const w of words) for (let i = 0; i < w.length; i++) coeff[w[w.length-1-i]] = (coeff[w[w.length-1-i]] ?? 0) + Math.pow(10, i);
    for (let i = 0; i < result.length; i++) coeff[result[result.length-1-i]] = (coeff[result[result.length-1-i]] ?? 0) - Math.pow(10, i);
    const used = Array(10).fill(false);
    const charToDigit: Record<string, number> = {};
    function backtrack(idx: number): boolean {
        if (idx === chars.length) {
            let total = 0;
            for (const c in coeff) total += coeff[c] * charToDigit[c];
            return total === 0;
        }
        const c = chars[idx];
        for (let d = 0; d < 10; d++) {
            if (used[d]) continue;
            if (d === 0 && firstLetters.has(c)) continue;
            charToDigit[c] = d; used[d] = true;
            if (backtrack(idx + 1)) return true;
            used[d] = false; delete charToDigit[c];
        }
        return false;
    }
    return backtrack(0);
}

Complexity

• ⏰ Time complexity: O(10^n * L) where n is the number of unique letters (≤10), L is the total length of all words.
• 🧺 Space complexity: O(n) for recursion and mappings.

Method 2 – Column-wise Carry Backtracking (Pruned DFS)

Intuition

We can prune vastly more by simulating the addition column by column (least significant to most), carrying over as in grade-school arithmetic. At each column we only consider the digits for letters that appear in that column whose digits are still unassigned; once all addend letters in a column are resolved we know the required digit (and carry) for the result letter—reject early if conflicting. This avoids exploring assignments that would only later violate the linear sum.

Approach

Let maxLen = max(len(word) for word in words + [result]).

Recursive function dfs(col, rowIndex, carry):

• If col == maxLen → success if carry == 0.
• If rowIndex < len(words): we are processing addend rows at current column.
  • If col >= len(words[rowIndex]) (word shorter) → just move to next row.
  • Else consider letter ch = words[rowIndex][-1-col]:
    • If assigned: accumulate its digit into a running columnSum and move to next row.
    • Else iterate candidate digits (skip used / leading-zero). Assign, recurse; backtrack.
• If rowIndex == len(words): handle result letter at this column.
  • Compute expected = columnSum + carry.
  • Required digit d = expected % 10, new carry nc = expected / 10.
  • Let rch = result[-1-col] if column exists else treat as overflow → fail unless no remaining digits and expected forms exact leftover carry.
  • If rch already assigned: must match d, then recurse to next column with dfs(col+1, 0, nc).
  • Else assign digit d (respect leading-zero rule), recurse, backtrack.

We maintain per-column columnSum via function argument or closure accumulation.

Ordering letters by usage frequency can further prune, but core column recursion already slashes search space.

Worked Example (SEND + MORE = MONEY)

Key early deductions without writing any full permutation:

1. Result has one extra digit → final carry out of the highest processed column must be 1, so M = 1 (and cannot be any other digit). This immediately marks a digit as used and enforces a future carry.
2. Column equations right→left (with carry c):
   • Units: D + E + c ≡ Y (mod 10); new carry ⌊(D+E+c)/10⌋.
   • Tens: N + R + c ≡ E (mod 10).
   • Hundreds: E + O + c ≡ N (mod 10).
   • Thousands: S + M + c ≡ O (mod 10) (with M already fixed =1).
   • Ten‑Thousands: leftover carry must equal M (which is 1) → consistency check.
3. Leading‑zero rule applies to S, M, and the result's first letter (M).
4. The Method 2 DFS enforces exactly these modular constraints on the fly: once all addend letters in a column are assigned, the result letter digit is forced; mismatch → immediate backtrack.

This concise reasoning is pedagogical; we avoid a duplicate specialized solver (the generic Method 2 code already handles the two‑addend case). For classroom exposition you can print the modular equations; implementation stays unchanged.

Pseudocode

dfs(col, row, carry, columnSum):
    if col == maxLen: return carry == 0
    if row < numWords:
        if col >= len(words[row]):
            return dfs(col, row+1, carry, columnSum)
        ch = words[row][-1-col]
        if ch assigned:
            return dfs(col, row+1, carry, columnSum + digit[ch])
        for d in 0..9 not used:
            if d == 0 and ch is leading multi-letter: continue
            assign ch=d
            if dfs(col, row+1, carry, columnSum + d): return true
            unassign ch
        return false
    # result row
    if col >= len(result): return false  # extra carry mismatch
    rch = result[-1-col]
    expected = columnSum + carry
    d = expected % 10
    nc = expected / 10
    if rch assigned:
        if digit[rch] != d: return false
        return dfs(col+1, 0, nc, 0)
    if d used or (d==0 and rch leading multi-letter): return false
    assign rch=d
    if dfs(col+1, 0, nc, 0): return true
    unassign rch
    return false

Code

Python

from typing import List
class Solution:
    def isSolvable(self, words: List[str], result: str) -> bool:
        words = [w for w in words]
        max_len = max(max(len(w) for w in words), len(result))
        letters = set(''.join(words) + result)
        if len(letters) > 10: return False
        leading = {w[0] for w in words if len(w) > 1}
        if len(result) > 1: leading.add(result[0])
        digit = {}
        used = [False]*10

        def dfs(col: int, row: int, carry: int, colsum: int) -> bool:
            if col == max_len:
                return carry == 0
            if row < len(words):
                w = words[row]
                if col >= len(w):
                    return dfs(col, row+1, carry, colsum)
                ch = w[-1-col]
                if ch in digit:
                    return dfs(col, row+1, carry, colsum + digit[ch])
                for d in range(10):
                    if used[d]: continue
                    if d == 0 and ch in leading: continue
                    digit[ch] = d; used[d] = True
                    if dfs(col, row+1, carry, colsum + d): return True
                    used[d] = False; del digit[ch]
                return False
            # result row
            if col >= len(result):
                return False  # cannot have unmatched carry column
            rch = result[-1-col]
            expected = colsum + carry
            d = expected % 10
            nc = expected // 10
            if rch in digit:
                if digit[rch] != d: return False
                return dfs(col+1, 0, nc, 0)
            if used[d]:
                return False
            if d == 0 and rch in leading: return False
            digit[rch] = d; used[d] = True
            if dfs(col+1, 0, nc, 0): return True
            used[d] = False; del digit[rch]
            return False

        return dfs(0, 0, 0, 0)

Java

import java.util.*;
class Solution2 { // alternative optimized solver
    public boolean isSolvable(String[] words, String result) {
        int maxLen = result.length();
        for (String w : words) maxLen = Math.max(maxLen, w.length());
        Set<Character> letters = new HashSet<>();
        for (String w : words) for (char c: w.toCharArray()) letters.add(c);
        for (char c: result.toCharArray()) letters.add(c);
        if (letters.size() > 10) return false;
        Set<Character> leading = new HashSet<>();
        for (String w: words) if (w.length() > 1) leading.add(w.charAt(0));
        if (result.length() > 1) leading.add(result.charAt(0));
        int[] assign = new int[26]; Arrays.fill(assign, -1);
        boolean[] used = new boolean[10];

        return dfs(words, result, maxLen, 0, 0, 0, 0, assign, used, leading);
    }

    private boolean dfs(String[] words, String result, int maxLen,
                        int col, int row, int carry, int colSum,
                        int[] assign, boolean[] used, Set<Character> leading) {
        if (col == maxLen) return carry == 0; // all columns processed
        if (row < words.length) {
            String w = words[row];
            if (col >= w.length()) {
                return dfs(words, result, maxLen, col, row+1, carry, colSum, assign, used, leading);
            }
            char ch = w.charAt(w.length()-1-col);
            int idx = ch - 'A';
            if (assign[idx] != -1) {
                return dfs(words, result, maxLen, col, row+1, carry, colSum + assign[idx], assign, used, leading);
            }
            for (int d = 0; d < 10; ++d) {
                if (used[d]) continue;
                if (d == 0 && leading.contains(ch)) continue;
                assign[idx] = d; used[d] = true;
                if (dfs(words, result, maxLen, col, row+1, carry, colSum + d, assign, used, leading)) return true;
                used[d] = false; assign[idx] = -1;
            }
            return false;
        }
        // result row
        if (col >= result.length()) return false; // no place for carry digits
        char rch = result.charAt(result.length()-1-col);
        int ridx = rch - 'A';
        int expected = colSum + carry;
        int d = expected % 10;
        int nextCarry = expected / 10;
        if (assign[ridx] != -1) {
            if (assign[ridx] != d) return false;
            return dfs(words, result, maxLen, col+1, 0, nextCarry, 0, assign, used, leading);
        }
        if (used[d]) return false;
        if (d == 0 && leading.contains(rch)) return false;
        assign[ridx] = d; used[d] = true;
        if (dfs(words, result, maxLen, col+1, 0, nextCarry, 0, assign, used, leading)) return true;
        used[d] = false; assign[ridx] = -1;
        return false;
    }
}

C++

class Solution2 { // optimized column-wise solver
public:
    bool isSolvable(vector<string>& words, string result) {
        int maxLen = result.size();
        for (auto &w: words) maxLen = max<int>(maxLen, w.size());
        unordered_set<char> letters;
        for (auto &w: words) for (char c: w) letters.insert(c);
        for (char c: result) letters.insert(c);
        if (letters.size() > 10) return false;
        unordered_set<char> leading;
        for (auto &w: words) if (w.size() > 1) leading.insert(w[0]);
        if (result.size() > 1) leading.insert(result[0]);
        array<int,26> assign; assign.fill(-1);
        array<bool,10> used{}; used.fill(false);
        return dfs(words, result, maxLen, 0, 0, 0, 0, assign, used, leading);
    }
private:
    bool dfs(vector<string>& words, string &result, int maxLen,
             int col, int row, int carry, int colSum,
             array<int,26>& assign, array<bool,10>& used, unordered_set<char>& leading) {
        if (col == maxLen) return carry == 0;
        if (row < (int)words.size()) {
            string &w = words[row];
            if (col >= (int)w.size()) return dfs(words, result, maxLen, col, row+1, carry, colSum, assign, used, leading);
            char ch = w[w.size()-1-col];
            int idx = ch - 'A';
            if (assign[idx] != -1) return dfs(words, result, maxLen, col, row+1, carry, colSum + assign[idx], assign, used, leading);
            for (int d=0; d<10; ++d) {
                if (used[d]) continue;
                if (d==0 && leading.count(ch)) continue;
                assign[idx]=d; used[d]=true;
                if (dfs(words, result, maxLen, col, row+1, carry, colSum + d, assign, used, leading)) return true;
                used[d]=false; assign[idx]=-1;
            }
            return false;
        }
        if (col >= (int)result.size()) return false;
        char rch = result[result.size()-1-col];
        int ridx = rch - 'A';
        int expected = colSum + carry;
        int d = expected % 10;
        int nextCarry = expected / 10;
        if (assign[ridx] != -1) {
            if (assign[ridx] != d) return false;
            return dfs(words, result, maxLen, col+1, 0, nextCarry, 0, assign, used, leading);
        }
        if (used[d]) return false;
        if (d==0 && leading.count(rch)) return false;
        assign[ridx]=d; used[d]=true;
        if (dfs(words, result, maxLen, col+1, 0, nextCarry, 0, assign, used, leading)) return true;
        used[d]=false; assign[ridx]=-1;
        return false;
    }
};

Complexity

• ⏰ Time complexity: O(branch^C) where C = number of columns; in practice far less than 10^n due to early carry pruning (often milliseconds for typical inputs). Worst theoretical still exponential in unique letters.
• 🧺 Space complexity: O(n + depth) – assignment arrays plus recursion stack depth up to maxLen.

Method Comparison

Method	Idea	Pruning	When to Teach	Time (practical)	Space
1 Coefficient Backtracking	Linear sum = 0; assign all then check	Minimal (only leading + used digits)	Intro to mapping/permutations	Slow on dense 10-letter cases	O(n)
2 Column-wise Carry	Simulate grade-school addition with carry	High (rejects early column mismatches)	After grasping Method 1	Typically milliseconds	O(n + depth)
Two-Addend Walkthrough	Didactic specialization of Method 2	Same as Method 2 (simpler state)	First exposure / classroom	Very fast	O(n)