Verbal Arithmetic Puzzle - Video Solutions
Leetcode 1307: Verbal Arithmetic Puzzle (Leetcode Hard)
Verbal Arithmetic Puzzle - Video Solution
Watch 5 video solutions for Verbal Arithmetic Puzzle, a hard level problem involving Array, Math, String. This walkthrough by Algorithms Casts has 5,049 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
Problem Statement
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]andresultare 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.
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 <= 51 <= words[i].length, result.length <= 7words[i], resultcontain only uppercase English letters.- The number of different characters used in the expression is at most
10.
Approach Overview
Problem Overview: You are given several words representing numbers where each character maps to a unique digit (0–9). The goal is to determine whether a digit assignment exists such that the sum of the first n‑1 words equals the final word. Leading characters cannot map to zero, and every letter must map to a distinct digit.
Approach 1: Backtracking Search (Exponential, ~O(10!) time, O(1) space)
This approach treats the puzzle as a digit assignment problem. First collect all unique characters across the input words. Then recursively assign digits from 0–9 while maintaining a used set so no digit is reused. After assigning digits to all characters, convert each word into a number and check whether the arithmetic equation holds. The key pruning rule prevents assigning 0 to leading characters. This brute-force backtracking search explores permutations of digits but prunes many invalid states early.
Approach 2: Constraint Satisfaction with Bit Masking (Optimized Backtracking, ~O(10!) worst case, O(1) space)
A more structured solution evaluates the equation column by column from right to left, similar to manual addition. Instead of constructing full numbers, maintain the running column sum and propagate carry values during recursion. A bit mask tracks which digits are already assigned, enabling constant-time digit availability checks. This turns the problem into a constraint satisfaction system where partial assignments are validated immediately. Early pruning dramatically reduces the search space because invalid column sums are discarded before exploring deeper states. This method combines ideas from math, string processing, and constraint-based backtracking.
Recommended for interviews: Start by explaining the basic backtracking permutation idea since it demonstrates understanding of the search space and constraints. Then move to the column-wise constraint approach with bit masking. Interviewers prefer this optimized strategy because it prunes invalid assignments early and models the arithmetic addition directly, which significantly reduces unnecessary recursion.
Complexity Analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Backtracking Digit Assignment | O(10!) | O(1) | Good starting point to explain brute-force search and permutation generation |
| Constraint Satisfaction with Bit Masking | O(10!) worst case (heavily pruned) | O(1) | Preferred approach for interviews and competitive coding due to strong pruning |