LeetCode 1307 - Verbal Arithmetic Puzzle

The problem gives a collection of words on the left side of an equation and a single result word on the right side. Each distinct uppercase letter must be assigned a unique digit from 0 to 9.

leetcodehardarraymathstringbacktracking

LeetCode Problem 1307

Difficulty: 🔴 Hard
Topics: Array, Math, String, Backtracking

Solution

Problem Understanding

The problem gives a collection of words on the left side of an equation and a single result word on the right side. Each distinct uppercase letter must be assigned a unique digit from 0 to 9. After replacing every letter with its assigned digit, the numerical values represented by the left-side words must sum exactly to the numerical value represented by the result word.

For example, if we map:

  • S -> 9
  • E -> 5
  • N -> 6
  • D -> 7

then "SEND" becomes 9567.

The challenge is to determine whether there exists at least one valid assignment of digits that satisfies all constraints simultaneously.

The important constraints are:

  • Different letters must map to different digits.
  • Leading characters of multi-digit words cannot map to 0.
  • At most 10 distinct letters appear overall.

That final constraint is extremely important. Since there are only ten digits available, any solution must carefully search through assignments. A naive brute-force approach can still become prohibitively expensive because even 10! = 3,628,800 assignments are possible before validation costs are considered.

Another key observation is that this is essentially a column-by-column arithmetic puzzle, exactly like manual addition. Instead of building full numbers first, we can validate the addition digit by digit from right to left.

Several edge cases are especially important:

  • A leading character cannot become 0, even if doing so would satisfy the arithmetic.
  • The result word may be longer than all input words combined by one digit because of carry propagation.
  • Some puzzles contain fewer than ten letters but still have no valid assignment.
  • Multiple words may contribute digits to the same column.
  • Carry handling is critical because mistakes in carry propagation cause incorrect solutions.

Approaches

Brute Force Approach

The brute-force solution collects all distinct letters and tries every possible digit assignment using permutations of digits 0-9.

For each assignment:

  1. Ensure no leading letter maps to 0
  2. Convert every word into its numeric value
  3. Compute the sum of the left-side words
  4. Compare against the numeric value of result

This approach is correct because it exhaustively checks every possible valid mapping. If a valid assignment exists, brute force eventually finds it.

However, it is far too slow in the worst case. With up to ten unique characters, the algorithm may need to evaluate nearly 10! assignments. Additionally, every assignment requires reconstructing multiple integers repeatedly.

Key Insight for the Optimal Solution

The crucial observation is that arithmetic works column by column from right to left.

Instead of assigning all digits first and validating afterward, we can validate constraints incrementally while constructing assignments.

Suppose we process the equation like manual addition:

  SEND
+ MORE
------
 MONEY

Starting from the rightmost column:

D + E = Y

Then:

N + R + carry = E

At each column, we only need local consistency with the carry.

This enables aggressive pruning:

  • If a partial assignment already violates the arithmetic, we immediately stop exploring that branch.
  • We never construct invalid full assignments.
  • Carry propagation naturally constrains future choices.

This transforms the problem into an efficient backtracking search.

Approach Time Complexity Space Complexity Notes
Brute Force O(10! × k) O(10) Tries every digit permutation and validates afterward
Optimal O(10!) worst case, heavily pruned O(10) Column-wise backtracking eliminates invalid states early

Here, k represents the cost of constructing and validating numbers.

Algorithm Walkthrough

Step 1: Reverse the Words

We process addition from least significant digit to most significant digit, so reversing every word makes indexing easier.

For example:

SEND -> DNES
MORE -> EROM
MONEY -> YENOM

Now index 0 corresponds to the units place.

Step 2: Track Character Assignments

We maintain:

  • A mapping from character to digit
  • A boolean array indicating which digits are already used

This ensures uniqueness constraints are enforced efficiently.

A hash map is ideal because character lookup and updates are constant time.

Step 3: Identify Leading Characters

Any leading character of a multi-digit word cannot map to 0.

We store these characters in a set so we can quickly reject invalid assignments during backtracking.

Step 4: Process Column by Column

We recursively process:

  • Current column index
  • Current word index within that column
  • Current carry value

At each column:

  • Sum all digits from the left-side words
  • Compare against the required digit in the result word

This mirrors elementary addition exactly.

Step 5: Handle Assigned Characters

If a character already has a digit assignment:

  • Use that digit directly
  • Continue recursion

No additional branching is needed.

Step 6: Try Possible Digits for Unassigned Characters

If a character is unassigned:

  1. Iterate through digits 0-9
  2. Skip already-used digits
  3. Skip 0 for leading characters
  4. Tentatively assign the digit
  5. Recurse deeper
  6. Backtrack if necessary

Backtracking systematically explores all valid possibilities.

Step 7: Validate the Result Column

After summing all left-side digits in a column:

expected_digit = total % 10
new_carry = total // 10

The result character must equal expected_digit.

If it does not, the branch is impossible and is immediately pruned.

Step 8: Move to the Next Column

Once a column is validated:

  • Advance to the next column
  • Pass the carry forward

The recursion continues until all columns are processed.

Step 9: Final Validation

When all columns are processed:

  • The puzzle is solvable only if the final carry is 0

Otherwise, the arithmetic is incomplete.

Why it works

The algorithm maintains a strict invariant:

Every processed column satisfies valid arithmetic under the current assignments.

Because recursion only proceeds when each column is locally correct, any completed assignment automatically satisfies the entire equation globally. Since the search explores all valid assignments systematically, the algorithm is both correct and complete.

Python Solution

from typing import List

class Solution:
    def isSolvable(self, words: List[str], result: str) -> bool:
        reversed_words = [word[::-1] for word in words]
        reversed_result = result[::-1]

        leading_chars = set()

        for word in words:
            if len(word) > 1:
                leading_chars.add(word[0])

        if len(result) > 1:
            leading_chars.add(result[0])

        char_to_digit = {}
        used_digits = [False] * 10

        max_len = max(len(result), max(len(word) for word in words))

        def backtrack(column: int, row: int, current_sum: int) -> bool:
            if column == max_len:
                return current_sum == 0

            if row == len(reversed_words):
                result_char = (
                    reversed_result[column]
                    if column < len(reversed_result)
                    else None
                )

                digit = current_sum % 10
                carry = current_sum // 10

                if result_char in char_to_digit:
                    if char_to_digit[result_char] != digit:
                        return False

                    return backtrack(column + 1, 0, carry)

                if used_digits[digit]:
                    return False

                if digit == 0 and result_char in leading_chars:
                    return False

                char_to_digit[result_char] = digit
                used_digits[digit] = True

                if backtrack(column + 1, 0, carry):
                    return True

                del char_to_digit[result_char]
                used_digits[digit] = False

                return False

            if column >= len(reversed_words[row]):
                return backtrack(column, row + 1, current_sum)

            current_char = reversed_words[row][column]

            if current_char in char_to_digit:
                return backtrack(
                    column,
                    row + 1,
                    current_sum + char_to_digit[current_char]
                )

            for digit in range(10):
                if used_digits[digit]:
                    continue

                if digit == 0 and current_char in leading_chars:
                    continue

                char_to_digit[current_char] = digit
                used_digits[digit] = True

                if backtrack(
                    column,
                    row + 1,
                    current_sum + digit
                ):
                    return True

                del char_to_digit[current_char]
                used_digits[digit] = False

            return False

        return backtrack(0, 0, 0)

The implementation follows the exact column-wise recursive strategy described earlier.

The words and result are first reversed so that index 0 corresponds to the least significant digit. This simplifies traversal because arithmetic addition naturally proceeds from right to left.

The leading_chars set prevents illegal assignments where a multi-digit number begins with zero.

The recursive backtrack function has three parameters:

  • column, the current digit column
  • row, which word we are currently processing in that column
  • current_sum, the accumulated sum including carry

When all words in the current column have been processed, the algorithm validates the corresponding result digit. If the digit assignment is inconsistent, the branch is pruned immediately.

Unassigned characters are explored by trying all unused digits. After recursion returns, assignments are undone so alternative possibilities can be explored cleanly.

The recursion terminates successfully only when all columns are processed and no carry remains.

Go Solution

package main

func isSolvable(words []string, result string) bool {
	reversedWords := make([][]byte, len(words))

	maxLen := len(result)

	for i, word := range words {
		reversedWords[i] = reverse(word)

		if len(word) > maxLen {
			maxLen = len(word)
		}
	}

	reversedResult := reverse(result)

	leadingChars := make(map[byte]bool)

	for _, word := range words {
		if len(word) > 1 {
			leadingChars[word[0]] = true
		}
	}

	if len(result) > 1 {
		leadingChars[result[0]] = true
	}

	charToDigit := make(map[byte]int)
	usedDigits := make([]bool, 10)

	var backtrack func(column, row, currentSum int) bool

	backtrack = func(column, row, currentSum int) bool {
		if column == maxLen {
			return currentSum == 0
		}

		if row == len(reversedWords) {
			if column >= len(reversedResult) {
				return false
			}

			resultChar := reversedResult[column]

			digit := currentSum % 10
			carry := currentSum / 10

			if assignedDigit, exists := charToDigit[resultChar]; exists {
				if assignedDigit != digit {
					return false
				}

				return backtrack(column+1, 0, carry)
			}

			if usedDigits[digit] {
				return false
			}

			if digit == 0 && leadingChars[resultChar] {
				return false
			}

			charToDigit[resultChar] = digit
			usedDigits[digit] = true

			if backtrack(column+1, 0, carry) {
				return true
			}

			delete(charToDigit, resultChar)
			usedDigits[digit] = false

			return false
		}

		if column >= len(reversedWords[row]) {
			return backtrack(column, row+1, currentSum)
		}

		currentChar := reversedWords[row][column]

		if assignedDigit, exists := charToDigit[currentChar]; exists {
			return backtrack(
				column,
				row+1,
				currentSum+assignedDigit,
			)
		}

		for digit := 0; digit <= 9; digit++ {
			if usedDigits[digit] {
				continue
			}

			if digit == 0 && leadingChars[currentChar] {
				continue
			}

			charToDigit[currentChar] = digit
			usedDigits[digit] = true

			if backtrack(
				column,
				row+1,
				currentSum+digit,
			) {
				return true
			}

			delete(charToDigit, currentChar)
			usedDigits[digit] = false
		}

		return false
	}

	return backtrack(0, 0, 0)
}

func reverse(s string) []byte {
	n := len(s)
	reversed := make([]byte, n)

	for i := 0; i < n; i++ {
		reversed[i] = s[n-1-i]
	}

	return reversed
}

The Go implementation closely mirrors the Python version, but several language-specific details differ.

Go does not have built-in hash sets, so map[byte]bool is used for the leading character set.

Character assignments are stored using map[byte]int. Since Go distinguishes between missing keys and zero values, the code uses the two-value map lookup form:

value, exists := map[key]

Backtracking cleanup uses delete() to remove assignments cleanly.

Strings are converted into reversed byte slices because indexing bytes is more efficient and convenient than repeatedly slicing strings.

Integer overflow is not a concern because the maximum carry remains very small due to the problem constraints.

Worked Examples

Example 1

words = ["SEND", "MORE"]
result = "MONEY"

Reversed forms:

DNES
EROM
YENOM

Initial state:

Variable Value
column 0
carry 0
assignments {}

Processing column 0:

D + E = Y

Suppose recursion tries:

Character Digit
D 7
E 5

Then:

7 + 5 = 12

So:

Value Result
result digit 2
carry 1

Assign:

Character Digit
Y 2

Next column:

N + R + 1 = E

Suppose:

Character Digit
N 6
R 8

Then:

6 + 8 + 1 = 15

Result digit becomes 5, matching E.

Carry becomes 1.

The recursion continues until all columns satisfy arithmetic:

9567 + 1085 = 10652

The algorithm returns True.

Example 2

words = ["SIX", "SEVEN", "SEVEN"]
result = "TWENTY"

The recursion explores assignments column by column.

One successful mapping is:

Character Digit
S 6
I 5
X 0
E 8
V 7
N 2
T 1
W 3
Y 4

Which produces:

650 + 68782 + 68782 = 138214

The algorithm returns True.

Example 3

words = ["LEET", "CODE"]
result = "POINT"

The recursion systematically explores assignments but repeatedly encounters contradictions:

  • Digit conflicts
  • Invalid carries
  • Impossible result digits

Eventually all branches are exhausted without success.

The algorithm returns False.

Complexity Analysis

Measure Complexity Explanation
Time O(10!) worst case Backtracking may explore many digit assignments
Space O(10) Assignment maps and recursion depth are bounded by unique letters

Although the theoretical worst-case runtime is factorial, practical performance is much better because the column-by-column pruning removes invalid assignments extremely early. Most branches terminate long before all digits are assigned.

The space complexity remains small because there are at most ten unique characters.

Test Cases

sol = Solution()

assert sol.isSolvable(
    ["SEND", "MORE"],
    "MONEY"
) is True  # classic cryptarithm example

assert sol.isSolvable(
    ["SIX", "SEVEN", "SEVEN"],
    "TWENTY"
) is True  # multiple addends with carry chains

assert sol.isSolvable(
    ["LEET", "CODE"],
    "POINT"
) is False  # no valid mapping exists

assert sol.isSolvable(
    ["A", "B"],
    "C"
) is True  # simple one-digit addition

assert sol.isSolvable(
    ["A", "A"],
    "A"
) is False  # impossible because A+A cannot equal A

assert sol.isSolvable(
    ["AB", "BC"],
    "CD"
) is False  # conflicting carry constraints

assert sol.isSolvable(
    ["AA", "BB"],
    "CC"
) is True  # repeated letters handled correctly

assert sol.isSolvable(
    ["THIS", "IS", "TOO"],
    "FUNNY"
) is True  # larger valid puzzle

assert sol.isSolvable(
    ["A"],
    "A"
) is True  # trivial equality

assert sol.isSolvable(
    ["A"],
    "B"
) is True  # distinct single-digit assignments possible

assert sol.isSolvable(
    ["ABC", "DEF"],
    "GHI"
) is True  # many valid possibilities

assert sol.isSolvable(
    ["AAA", "AAA"],
    "AAA"
) is False  # carry contradiction
Test Why
SEND + MORE = MONEY Validates classic carry-heavy cryptarithm
SIX + SEVEN + SEVEN = TWENTY Tests multiple addends
LEET + CODE = POINT Ensures impossible puzzles return false
A + B = C Simple solvable case
A + A = A Tests arithmetic impossibility
AB + BC = CD Validates carry handling
AA + BB = CC Tests repeated character consistency
THIS + IS + TOO = FUNNY Larger recursion tree
A = A Minimal valid input
A = B Distinct assignments allowed
ABC + DEF = GHI Many valid assignments exist
AAA + AAA = AAA Impossible due to carry behavior

Edge Cases

Leading Zero Violations

A very common bug is accidentally allowing a leading character to map to 0.

For example:

SEND -> 0123

This is invalid because numbers cannot contain leading zeros.

The implementation prevents this by storing all leading characters in a set and rejecting any assignment where such a character receives digit 0.

Carry Propagation Across Multiple Columns

Some puzzles require carries to propagate through many columns consecutively.

For example:

999 + 1 = 1000

In verbal arithmetic form, similar carry chains are common. Incorrect carry handling causes subtle arithmetic errors.

The recursive algorithm explicitly computes:

digit = total % 10
carry = total // 10

for every column, ensuring carries propagate correctly.

Repeated Characters

A letter may appear many times across different words and columns.

For example:

AA + BB = CC

Every occurrence of the same character must always map to the same digit.

The implementation guarantees consistency using the char_to_digit map. Once a character receives a digit assignment, all future occurrences reuse that exact digit automatically.