Watch 6 video solutions for Verbal Arithmetic Puzzle, a hard level problem involving Array, Math, String. This walkthrough by Algorithms Casts has 4,982 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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:
words[i] and result are decoded as one number without leading zeros.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], result contain only uppercase English letters.10.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.
| 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 |